[백준] 1254. 펠린드롬 만들기 (자바 JAVA)

[ 문제 ]  [백준] 1254. 펠린드롬 만들기 (자바 JAVA)

 

문제 링크 : https://www.acmicpc.net/problem/1254

1254번: 팰린드롬 만들기

---

# 접근 방법 및 풀이 

 

• 이런 문제가 코테로 나오면 바로 풀었을까 싶은 문제다.. 대신 한번 풀어보면 쉽게 풀 수 있다.
• 문제대로 팰린드롬이란 "문자를 앞으로 읽어도 뒤로 읽어도 같게 읽히는 문자열"이다.
• 먼저, 문자열이 펠린드롬인지 확인하는 함수를 만든다. 펠린드롬인지 확인하는 방법은 "앞의 인덱스와(start)" "뒤의 인덱스(last)"를 차례대로 비교하면 된다.

• a

  a

  b

  a

  a

• 위와같이 같은 색상으로 칠해진 앞 뒤 문자로 비교할 것이고, 펠린드롬일 경우엔 현재 길이 5가 정답이 된다.
• 그러나 그렇지 않을땐, 주어진 문자열에서 앞에서부터 문자를 하나씩 잘라보며 펠린드롬을 찾아야한다.
• "aabb"일 경우, 길이는 4이며 현재 펠린드롬이 아니다. 

• a

  a

  b

  b

• a

  b

  b

• b

  b

• 이렇게 앞의 문자를 하나씩 잘라 만든 문자열이 펠린드롬인지 찾고,  "bb"일때 펠린드롬을 찾을 수 있다. 펠린드롬을 찾았을 경우, 펠린드롬이 시작하는 문자열 왼쪽에 있는 길이만큼 오른쪽에 붙여주면 펠린드롬이 되고 그때의 길이가 정답이다.
• 따라서 "aabb"는 "aabbaa"로 길이가 6이 됐을때 펠린드롬이다.
• 쉽게 주어진 문자열에서, "_ _ _ _ _ aaa" 펠린드롬을 발견한 순간, 대칭이 되도록 오른쪽에 발견한 펠린드롬 왼쪽의 글자수만큼 붙는다고 생각하면 쉽다. "_ _ _ _ _ aaa _ _ _ _ _ "
• aaa라는 펠린드롬 왼쪽의 글자수가 5개이므로 aaa의 오른쪽에 5개의 글자수가 붙는다.
• 이렇게 이 문제의 핵심은 주어진 문자열 속 펠린드롬을 찾고, 펠린드롬의 왼쪽의 길이만큼 오른쪽에 덧 붙여 총 길이를 찾으면된다.
• 자세한건 코드참조

 

# 주의할 점 

 

• 잘 생각해보기..어려웠다.

 

JAVA 코드

package Silver;

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

public class bj1254_펠린드롬만들기 {
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		String s = in.readLine();
		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 last = s.length()-1;
		while(start <= last) {
			if(s.charAt(start) != s.charAt(last))
				return false;
			start++;
			last--;
		}
		return true;
	}
}

 

 

 

REVIEW