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

문제

팰린드롬은 어느 방향으로 읽어도 항상 같은 방법으로 읽을 수 있는 단어이다. 예를 들어, civic, radar, rotor, madam은 팰린드롬이다.

상근이는 단어 k개 적혀있는 공책을 발견했다. 공책의 단어는 ICPC 문제가 저장되어 있는 서버에 접속할 수 있는 비밀번호에 대한 힌트이다. 비밀번호는 k개의 단어 중에서 두 단어를 합쳐야 되고, 팰린드롬이어야 한다. 예를 들어, 단어가 aaba, ba, ababa, bbaa, baaba일 때, ababa와 ba를 합치면 팰린드롬 abababa를 찾을 수 있다.

단어 k개 주어졌을 때, 팰린드롬을 찾는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 공책에 적혀져있는 단어의 수 k(1 ≤ k ≤ 100)가 주어진다. 다음 k개 줄에는 a부터 z까지 알파벳으로 이루어진 단어가 한 줄에 하나씩 주어진다. 모든 단어 길이의 합은 10,000보다 작거나 같다.

출력

각 테스트 케이스마다 팰린드롬을 출력한다. 만약, 가능한 팰린드롬이 여러 가지라면 아무거나 출력한다. 팰린드롬을 만들 수 없는 경우에는 0을 출력한다.

예제 입력

2
5
aaba
ba
ababa
bbaa
baaba
3
abc
bcd
cde

예제 출력

abababa
0

코드

import java.io.*;

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 T = Integer.parseInt(br.readLine());

        for (int test = 0; test < T; test++) {
            int k = Integer.parseInt(br.readLine());
            String[] words = new String[k];
            boolean possible = false;

            for (int i = 0; i < k; i++) {
                words[i] = br.readLine();
            }

            loop:
            for (int i = 0; i < k; i++) {
                for (int j = 0; j < k; j++) {
                    if (i == j) {
                        continue;
                    }
                    String new_word = words[i].concat(words[j]);

                    if (isPalindrome(new_word)) {
                        bw.write(new_word + "\n");
                        possible = true;
                        break loop;
                    }
                }
            }

            if (!possible) {
                bw.write(0 + "\n");
            }
        }

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

    static boolean isPalindrome(String word) {
        int n = word.length();
        for (int i = 0; i < (n / 2); i++) {
            if (word.charAt(i) != word.charAt(n - i - 1)) {
                return false;
            }
        }
        return true;
    }
}

정리

알고리즘
1. 이중 for 문을 돌면서 문자열을 붙인다.
2. 합쳐진 문자열이 Palindrome 인지 확인한다.
   - 문자열을 반으로 나눠서 앞뒤 같은지 확인
3. true 면 출력하고 break, for 문을 모두 돌았을 때 false 이면 0을 출력한다.