[Java] 백준 1254 팰린드롬 만들기 - 실버2

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

1254번: 팰린드롬 만들기

 

내 풀이 설명

• 나올 수 있는 가장 짧은 경우는
  • 짝수길이일 때: 짝수길이 팰린드롬으로 만들어지는 경우 (ex. baab) 
  • 홀수길이일 때: 홀수길이 팰린드롬으로 만들어지는 경우 (ex. bbabb) 
• 문자열 길이가 L이라면 L/2 - 1 인덱스부터 짝수길이 팰린드롬/ 홀수길이 팰린드롬을 만들어보고 인덱스를 하나씩 늘려가면서 비교한다
  • L/2 - 1 인덱스가 가장 짧은 경우이고 인덱스가 하나씩 늘어날수록 팰린드롬 길이가 늘어난다
  • 마지막 자리일 때 홀수길이 팰린드롬이 만들어지면 가장 긴 경우임

 

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

//[baekjoon] java-4375
public class Main {

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

    if (S.length() == 1) {
      System.out.println(1);
      return;
    }

    for (int i = S.length()/2 -1; i<S.length(); i++) {
      //홀수인 경우
      int left = i-1;
      int right = i+1;
      int pair = 0;

      while (left >=0 && right < S.length() && S.charAt(left) == S.charAt(right)) {
        left--;right++;pair ++;
      }

      if (right == S.length()) {
        System.out.println(2* S.length() - 1 - pair*2);
        return;
      }

      //짝수인 경우
      if (i+1 < S.length() && S.charAt(i) == S.charAt(i+1)) {
        left = i-1;
        right = i+2;
        pair = 1;

        while (left >=0 && right < S.length() && S.charAt(left) == S.charAt(right)) {
          left--;right++;pair ++;
        }

        if (right == S.length()) {
          System.out.println(2 * S.length() - pair*2);
          return;
        }
      }
    }
  }
}

• 홀수인 경우 left = i-1 / right = i+1로 시작하여 대칭되는지 계속 확인한다
• 짝수인 경우 left = i-1 / right = i+2로 시작하여 대칭되는지 확인
• 만약 right가 마지막자리를 넘어섰다면 팰린드롬이 만들어지는 경우이므로 해당 인덱스 기준으로 만들수 있는 경우를 출력 후 return 한다

 

솔직히 제한시간이 있고, 풀이를 생각할 종이가 없었다면 맞추기 힘들었을 것 같다. 

그래서 다른 풀이를 찾아봤음

 

 

다른풀이1 - 앞에서 한 글자씩 빼면서 팰린드롬 만들기

참고 블로그: https://cow-kite24.tistory.com/m/207

• 팰린드롬이 되는지 확인하고, 안되면 앞에 한글자씩 빼주는 방법이다
  • 구글링을 해보면 대부분 이 풀이를 사용하시는 걸 볼 수 있음
• 길이가 짝수일 때, 홀수일 때 나눠서 팰린드롬을 만들 수 있어서 훨씬 직관적인 방법인 것 같다

 

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

//[baekjoon] java-4375
public class Main {

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String s = br.readLine();
    int idx = 0;

    while (idx < s.length()) {
      //팰린드롬 되는지 확인
      if (isPalindrome(s, idx))
        break;

      idx ++;
    }

    System.out.println(idx*2 + s.length()-idx);
  }

  public static boolean isPalindrome(String s, int idx) {
    boolean isPalindrome = false;

    int left = idx;
    int right = s.length() - 1;

    if ((s.length() - idx) % 2 == 0) { //짝수인 경우
      while (left <= right) {
        if (s.charAt(left) != s.charAt(right))
          break;

        left++; right--;
      }

      if (left > right)
        isPalindrome = true;

    } else { //홀수인 경우
      while (left < right) {
        if (s.charAt(left) != s.charAt(right))
          break;

        left++; right--;
      }

      if (left == right)
        isPalindrome = true;
    }

    return isPalindrome;
  }
}

 

 

• 시간도 비슷하게 나오고 코드도 훨씬 직관적이라 이 풀이가 좋은 것 같음