[Baekjoon/Java] 1254번 팰린드롬 만들기

문제

동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 규완이는 팰린드롬을 엄청나게 좋아한다. 팰린드롬이란 앞에서부터 읽으나 뒤에서부터 읽으나 같게 읽히는 문자열을 말한다.

동호는 규완이를 위한 깜짝 선물을 준비했다. 동호는 규완이가 적어놓고 간 문자열 S에 0개 이상의 문자를 문자열 뒤에 추가해서 팰린드롬을 만들려고 한다. 동호는 가능하면 가장 짧은 문자열을 만들려고 한다.

동호가 만들 수 있는 가장 짧은 팰린드롬의 길이를 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 최대 50이다.

 

출력

첫째 줄에 동호가 만들 수 있는 가장 짧은 팰린드롬의 길이를 출력한다.

 

문제 풀이

 

첫번째 풀이 - 맞았습니다!!

사실 도저히 어떻게 풀어도 테케에서 걸릴 것 같아서 알고리즘이 쉽게 생각나지 않았다 ㅠ

그래서 다른 사람의 풀이를 참고해버렸다 ..

 

일단 예시로 abba 와 같은 케이스가 주어졌다면 이는 펠린드롬 수이기 때문에 ( a b | b a -> 대칭) 4를 출력해주면 되지만

abab 같은 케이스는 a b a b a 로 a를 추가해줘야 펠린드롬 수가 되고 이는 5를 출력하면 된다.

 

내가 참고했던 코드에서는 문자열의 양쪽 끝을 비교한다.

왼쪽 끝인 start = 0, 오른쪽 끝인 end = n(n은 문자열의 길이 - 1) 을 비교해서 만약 같다면 start++, end-- 을 하는 것이었다.

이 때 start > end라면 문자열 비교가 끝난 것이기 때문에 이는 펠린드롬의 수를 의미하고 실행을 종료하면 된다.

 

하지만 이 때 start <= end인 상태에서 S.charAt(start)와 S.charAt(end)이 같지 않다면 false를 반환하고

현재 문자열의 가장 앞부분을 빼고 남은 문자열로 다시 반복해주면 된다.

 

코드

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		String S = sc.next();
		int ans = S.length();
		
		for(int i=0; i<S.length(); i++) {
			if(isPalind(S.substring(i))) {
				break;
			}
			ans++;
		}
		System.out.println(ans);
	}

	private static boolean isPalind(String S) {
		int start = 0;
		int end = S.length()-1;
		
		while(start <= end) {
			if(S.charAt(start) != S.charAt(end)) {
				return false;
			}
			start++;
			end--;
		}
		
		return true;
	}
}

 

새롭게 알게 된 점 & 느낀점

생각하지 못 했던 알고리즘이라서 참고했을 때 헉.. 했고 언젠간 써먹을 수 있도록 꼭 기억해둬야겠다.

내가 문자열에 대해 약하다는 것을 알았고 이제 틈틈히 문자열에 대한 문제들을 풀어서 실력을 키워야겠다.

문자열 문제를 보고 겁 먹는 것도 해결하기 ㅎㅎ

 

 

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

1254번: 팰린드롬 만들기