[백준] 1254 팰린드롬 만들기 - 문자열(String) + 브루트포스(BruteForce) JAVA

https://www.acmicpc.net/problem/1254

코드설명

문자열(String) + 브루트포스(BruteForce) 를 활용합니다.

 

기본적인 아이디어는 주어진 문자열을 S라고 합시다.

그리고 팰린드롬을 체크하기 위하여 SReversed 라는 S를 뒤집은 문자열을 하나 생성합니다.

 

그리고 이 S와 SReversed를 비교하면 됩니다.

물론, 이때 이 S의 접미사와 SReversed의 접두사가 일치할떄 팰린드롬이 만들어지므로 Index를 잘 구현해서 처리해야겠지요.

코드

정답코드1입니다. 가장 단순한 문자열 검색 알고리즘이라고 할 수 있지요. 단어 S의 접미사에서 팰린드롬의 접두사를 찾는 과정이 검색입니다.

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
	static int N, M, S, P, A, B, X, L, R, C, n, k, m, l, K, D, T;
	static int answer = 50 * 2;
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//		StringTokenizer st = new StringTokenizer(br.readLine());
		String s = br.readLine();
		sb = new StringBuilder(s);
		String sReversed = sb.reverse().toString();
		
		for(int begin = 0; begin < s.length(); begin++) {
			int matched = 0;
			for(int sRBegin = 0; sRBegin + begin < sReversed.length(); sRBegin ++) {
				if(s.charAt(begin + sRBegin) == sReversed.charAt(sRBegin)) {
					matched++;
				} else {
					matched = 0;
					break;
				}
			}
			answer = Math.min(answer, s.length() * 2 - matched);
		}
		
		System.out.println(answer);
	}
	
}

정답코드2입니다. 이 코드는 정답코드1과 거의 같지만 비교하는 부분에서 로직이 살짝 다릅니다.

다른점은 begin + sRBegin 과 같이 Index를 처리하는 대신에 Substring해서 처리하는데요, 당연히 첫번쨰 코드가 더 효율적입니다.

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
	static int N, M, S, P, A, B, X, L, R, C, n, k, m, l, K, D, T;
	static int answer = 50 * 2;
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//		StringTokenizer st = new StringTokenizer(br.readLine());
		String s = br.readLine();
		sb = new StringBuilder(s);
		String sReversed = sb.reverse().toString();
		
		for(int begin = 0; begin < s.length(); begin++) {
			String sSub = s.substring(begin); //변경된 부분
			int matched = 0;
			for(int sRBegin = 0; sRBegin + begin < sReversed.length(); sRBegin ++) {
				if(sSub.charAt(sRBegin) == sReversed.charAt(sRBegin)) { //변경된 부분.
					matched++;
				} else {
					matched = 0;
					break;
				}
			}
			answer = Math.min(answer, s.length() * 2 - matched);
		}
		
		System.out.println(answer);
	}
	
}