[BOJ] 17609 회문 - JAVA

1. 문제

17609번: 회문

회문(回文) 또는 팰린드롬(palindrome)은 앞 뒤 방향으로 볼 때 같은 순서의 문자로 구성된 문자열을 말한다. 예를 들어 ‘abba’ ‘kayak’, ‘reviver’, ‘madam’은 모두 회문이다. 만일 그 자체는 회문이 아니지만 한 문자를 삭제하여 회문으로 만들 수 있는 문자열이라면 우리는 이런 문자열을 “유사회문”(pseudo palindrome)이라고 부른다. 예를 들어 ‘summuus’는 5번째나 혹은 6번째 문자 ‘u’를 제거하여 ‘summus’인 회문이 되므로 유사회문이다.

여러분은 제시된 문자열을 분석하여 그것이 그 자체로 회문인지, 또는 한 문자를 삭제하면 회문이 되는 “유사회문”인지, 아니면 회문이나 유사회문도 아닌 일반 문자열인지를 판단해야 한다. 만일 문자열 그 자체로 회문이면 0, 유사회문이면 1, 그 외는 2를 출력해야 한다. 

---

2. 풀이

solve 메서드만 설명한다.

1.  기본적으로 투포인터 풀이다. word[l]==word[r]이면 양쪽 끝을 전부 움직인다.

2.  그 외의 경우, count가 이미 1이라면 2를 반환하고 끝낸다.(count=2가 되기 때문)

3.  count가 0이었다면 (l, r-1)과 (l+1, r)이 두 구간을 전부 검사해서 더 작은 쪽을 반환한다.

4.  위의 경우에 걸리지 않았다면 그대로 count를 리턴한다.

import java.io.*;

public class BOJ_17609_회문 {
   static char[] word;
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      int N = Integer.parseInt(in.readLine());
      StringBuilder sb = new StringBuilder();

      int count;
      for(int i=0;i<N;i++){
         word = in.readLine().toCharArray();
         count = solve(0,word.length-1,0);
         sb.append(count).append('\n');
      }

      System.out.print(sb);
   }

   public static int solve(int left, int right, int count){
      int l = left;
      int r = right;
      while(l<r){
         if(word[l]==word[r]){
            l++; r--;
            continue;
         }

         if(count==1) return 2;
         return Math.min(solve(l,r-1,1), solve(l+1,r,1));
      }

      return count;
   }
}

---

3. 결과

첫번째는, 양쪽에서 하나씩 비교하다가 틀리면 l+1==r, l==r-1인지 테스트해서 그 방향으로 움직였다. 

두번째는, 회문체크 + 틀리면 무조건 오른쪽 + 틀리면 무조건 왼쪽 이렇게 세번 체크해서 맞았다.

세번째는, 다른 사람 코드를 참고했다. 재귀를 추가한건데, 본문 코드다! 두번째 코드 제출하면서 코드가 더러워서 찝찝했는데, 그걸 해결하는 방법이다.