백준 - 17609 회문(Java)

구현 문제입니다.

 

각 테스트 케이스에서 문장이 주어질 때, 해당 문장이 회문 or 유사 회문 or 일반 문장인지 확인하는 문제입니다.

• 회문일 경우 0
• 유사 회문일 경우 1
• 일반 문장일 경우 2

회문을 판단하는 방법은 앞, 뒤의 문자를 확인하면 됩니다.

for(int i=0; i < (n/2); i++){
    if(senChars[i] != senChars[n-1-i]){
        // 앞, 뒤 문자가 같지 않을 경우(회문이 아닌 경우)
    }
}

 

문제 접근 순서는 다음과 같습니다.

1. 큐에 문장을 넣는다.
2. 문장이 회문인지 확인한다.
   1. 회문이 아니라면 회문이 아닌 곳을 기준으로 문장을 자른다.
   2. 자른 문장을 큐에 넣는다.
   3. 회문인지 확인한다.
3. 큐의 반복 횟수에 따라 회문 or 유사 회문 or 일반 문장을 판단한다.

그림과 같이 xabba 문장은 회문이 아닙니다.

때문에, 양쪽 끝 부터 비교하여 서로 다른 위치의 문자를 비교하여 문장을 잘라 회문을 비교하면 됩니다.

좌측 xabb는 회문이지만, abba는 회문이기 때문에 유사 회문인 것입니다.

 

 

[구현 코드]

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int testCase = Integer.parseInt(br.readLine());
        while (testCase-- > 0) {
            String input = br.readLine();

            bw.write(check(input) + System.lineSeparator());
        }

        bw.flush();
        bw.close();
        br.close();
    }

    private static int check(String input) {
        Queue<String> qu = new LinkedList<>();
        qu.add(input);
        int cnt = 0;

        while (!qu.isEmpty()){
            String sentence = qu.poll();

            int[] palin = isPalindrome(sentence);

            // 회문일 경우
            if(palin == null){
                // 유사 회문일 경우
                if(cnt == 2) cnt--;
                break;
            }
            // 유사 회문도 아닐경우
            if(cnt > 1){
                cnt = 2;
                break;
            }

            cnt++;
            int lp = palin[0];
            int rp = palin[1];

            String leftPartition = sentence.substring(lp, rp);
            String rightPartition = sentence.substring(lp+1, rp+1);
            qu.add(leftPartition);
            qu.add(rightPartition);
        }

        return cnt;
    }

    private static int[] isPalindrome(String sentence) {
        char[] senChars = sentence.toCharArray();
        int n = senChars.length;

        for(int i=0; i < (n/2); i++){
            if(senChars[i] != senChars[n-1-i]){
                return new int[]{i, n-1-i};
            }
        }
        return null;
    }
}