[자바] 백준 8892 - 팰린드롬 (boj java)

문제 : boj8892

 

  각 테스트케이스마다 k가 최대 100개이므로, 모든 쌍을 보더라도 O(T x 100^2)번에 가능하다. 또한 모든 단어의 길이의 합은 10,000이하라고 했으므로, 단어 길이의 합을 L이라 할 때 팰린드롬인지 확인하는 로직이 O(L)짜리 로직이라 하더라도 O(TL x 100^2)으로 가능하다. 또한 팰린드롬인 값이 하나라도 있다면 거기서 종료하면 되므로, 대강 모든 경우를 봐도 시간내에 통과 가능할 것임을 예상할 수 있다.

 

  우선 문자열 S가 팰린드롬인지 확인하는 가장 간단한 방법은, |S/2|까지 인덱스를 증가하면서 앞과 뒤의 문자를 확인하는 것이다. isPalindrome() 함수를 확인해보면 알 수 있다.

 

  그리고 모든 경우를 보는 것은 모든 문자쌍을 만들어보면 된다. 코드의 26~40line을 확인해보자.

 

코드 : github

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

public class Main {
    private boolean isPalindrome(String a, String b) {
        String cur = a + b;
        boolean isPalindrome = true;
        for (int k = 0; k < cur.length()/2; k++) {
            if (cur.charAt(k) != cur.charAt(cur.length()-1-k)) {
                isPalindrome = false;
                break;
            }
        }
        return isPalindrome;
    }
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (tc-->0) {
            int n = Integer.parseInt(br.readLine());
            boolean chk = true;
            String[] arr = new String[n];
            for (int i = 0; i < n; i++) arr[i] = br.readLine();
            for (int i = 0; i < n-1 && chk; i++) {
                for (int j = i+1; j < n && chk; j++) {
                    if (i == j) break;
                    if (isPalindrome(arr[i], arr[j])) {
                        chk = false;
                        sb.append(arr[i]+arr[j]).append('\n');
                        break;
                    }
                    if (isPalindrome(arr[j], arr[i])) {
                        chk = false;
                        sb.append(arr[j]+arr[i]).append('\n');
                        break;
                    }
                }
            }
            if (chk) sb.append(0).append('\n');

        }
        System.out.print(sb);
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}