백준 - 팰린드롬

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.
저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

문의는 댓글 바람.

문제 출처 : https://www.acmicpc.net/problem/8892

단어 k개 중에서 2개를 붙였을 때, 그 수가 팰린드롬(앞에서 읽는 거랑 뒤에서 읽는 거랑 같으면)이면 그 문자를 출력하고, 없으면 0을 출력하시오.

 

[접근 방법]

언뜻 보면 k개의 단어 중 2개를 선택하는 순열 문제 같지만,

만약에 ab aba가 단어로 주어지면 ab+aba => ababa는 팰린드롬이지만 abaab는 팰린드롬이 아니다.

따라서 kC2(조합)가 아닌 kP2(순열)가 된다.

그러므로 시간 복잡도는 O(kP2).

kP2를 단순화하면 k!/(k-2)! => (k)(k-1)이므로 O(k^2-k) 시간복잡도는 최고차항만을 남기므로 시간복잡도는 O(k^2)이 된다.

 

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

public class Main {
    //    static int k = 2;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int cntOfTestcase = Integer.parseInt(br.readLine());
        for (int i = 1; i <= cntOfTestcase; i++) {
            int cntOfWords = Integer.parseInt(br.readLine());
            String[] words = new String[cntOfWords];
            for (int wordNo = 1; wordNo <= cntOfWords; wordNo++) {
                words[wordNo-1] = br.readLine();
            }

            if (!checkPalindrome(words)) System.out.println(0);
        }
    }

    private static boolean checkPalindrome(String[] words) {
        // 두 개를 선택하는 경우의 수 반복문
        for (int i = 0; i < words.length-1; i++) {
            for (int j = i+1; j < words.length; j++) {
                // 앞뒤를 번갈아가면서 붙여서 팰린드롬인지 체크
                String str = words[i].concat(words[j]);
                if (isPalindrome(str)) {
                    System.out.println(str);
                    return true;
                }

                str = words[j].concat(words[i]);
                if (isPalindrome(str)) {
                    System.out.println(str);
                    return true;
                }
            }
        }

        return false;
    }

    // 팰린드롬 체크하는 메서드
    private static boolean isPalindrome(String str) {
        for (int i = 0; i <= str.length()/2-1; i++) {
            if (str.charAt(i) != str.charAt(str.length()-i-1)) {
                return false;
            }
        }

        return true;
    }
}

[느낀 점]

조합을 구현해봐야겠다.

이것 단지 2개를 선택하는 거라 이중for문을 사용하여 단순하게 끝났지만, 만약 3개나 4개였다면 더 힘들었을 거다.

조합을 구현해보자.