[BOJ] 1254 팰린드롬 만들기 - JAVA

1. 문제

1254번: 팰린드롬 만들기

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

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

---

2. 풀이

Main

1.  문자열은 char배열로 만들어서 접근하기 편하게 만든다.

2.  길이를 하나씩 추가해가면서 탐색한다. check메서드에 len을 넣고 가능한지 파악하고, 가능하다면 출력하고 끝낸다.

static char[] input;
static int N;
public static void main(String[] args) throws IOException {
   BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
   input = in.readLine().toCharArray();
   N = input.length;

   for(int len = N;len<2*N;len++){
      if(check(len)){
         System.out.println(len);
         return;
      }
   }
}

 

Check

1.  check메서드는 길이를 입력받아서 그 가운데부터 한칸씩 멀어져가면서 탐색한다. 

2.  만약 길이가 짝수라면 가운데 값에서 -1을 해야 제대로 탐색할 수 있다.

3.  input[idx] 과 input[len-1-idx]를 비교해서 같지 않으면 바로 false를 반환한다.

4.  위에서 메서드가 끝나지 않았다면 true를 반환한다.

public static boolean check(int len){
   int idx = len/2;
   if(len%2==0) idx-=1;
   for(;idx>=0 && len-1-idx<N;idx--){
      if(input[idx] != input[len-1-idx]) return false;
   }
   return true;
}

 

전체 코드

import java.io.*;

public class BOJ_1254_팰린드롬만들기 {
   static char[] input;
   static int N;
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      input = in.readLine().toCharArray();
      N = input.length;

      for(int len = N;len<2*N;len++){
         if(check(len)){
            System.out.println(len);
            return;
         }
      }
   }

   public static boolean check(int len){
      int idx = len/2;
      if(len%2==0) idx-=1;
      for(;idx>=0 && len-1-idx<N;idx--){
         if(input[idx] != input[len-1-idx]) return false;
      }
      return true;
   }
}

---

3. 결과

짝수, 홀수 구분을 처음에만 해서 틀렸다.