[Baekjoon] 1254_팰린드롬 만들기

문제(출처: https://www.acmicpc.net/problem/1254)

---

< 팰린드롬 만기 >

 

문제 풀이 

 

짝수일 때와 홀수일 때를 고려해서 팰린드롬을 구한다.

 

* 사실 계속 틀려서 고치고 고치느라 나도 모르겠다

 

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class _1254_ { // 팰린드롬 만들기

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

		String S = bf.readLine();
		int answer = Integer.MAX_VALUE;

		boolean flag = false;
		if (S.length() == 1) {
			answer = 1;
		} else if (S.length() == 2 && S.charAt(0) == S.charAt(1)) {
			answer = 2;
		} else {
			for (int i = S.length() / 2 - 1; i < S.length(); i++) {
				boolean check = false;
				if (i + 1 < S.length() && S.charAt(i) == S.charAt(i + 1) && i>=S.length()-i-2) {
					for (int j = 1; j <= i; j++) {
						if (i + 1 + j >= S.length()) {
							answer = Math.min(answer, i + i + 2);
							flag = true;
							check = true;
							break;
						}
						if (S.charAt(i - j) != S.charAt(i + 1 + j)) {
							check = true;
							break;
						}
					}
					if (!check) {
						answer = Math.min(answer, S.length());
					}
				}

				if (i < S.length() - 1 - i) {
					continue;
				}

				check = false;
				for (int j = 1; j <= i; j++) {
					if (i + j >= S.length()) {
						answer = Math.min(answer, i + i + 1);
						flag = true;
						check = true;
						break;
					}
					if (S.charAt(i - j) != S.charAt(i + j)) {
						check = true;
						break;
					}
				}
				if (!check) {
					answer = Math.min(answer, S.length());
					break;
				}
				if (flag) {
					break;
				}
			}
		}
		System.out.println(answer);
	}
}

변수)
S : 문자열
answer : 가장 짧은 팰린드롬의 길이
flag : 팰린드롬 찾은 경우
check : 문자 추가 없이 팰린드롬인 경우

 

문자열을 입력받는다. 길이가 1일 때는 팰린드롬이므로 1을 출력하고 2일 때 똑같은 문자라면 2를 출력한다. 그 이외는

1) acca와 같은 짝수 팰린드롬을 구하기 위해 비교한다.

2) abcba와 같은 홀수 팰린드롬을 구하기 위해 비교한다.

 

 최종 만들 수 있는 가장 짧은 팰린드롬의 길이를 출력한다. 

---

---