[백준 1213] 팰린드롬 만들기 JAVA (문자열, 그리디, 구현)

1213번: 팰린드롬 만들기 (acmicpc.net)

1213번: 팰린드롬 만들기

문제를 요약해보자.

 

알파벳 대문자로 이루어진 문자열이 입력으로 들어온다.

    - 그 문자열로 팰린드롬을 만들 수 있다면, 가장 사전순으로 앞서는 팰린드롬을 출력한다.

    - 그 문자열로 팰린드롬을 만들 수 없다면, "I'm Sorry Hansoo" 를 출력한다.

 

여기서 팰린드롬이란 앞에서부터 읽든, 뒤에서부터 읽든 똑같이 읽히는 문자열을 의미한다. (예시: 🍎 토마토)

 

문자열의 길이는 최대 50 이고, 시간 제한은 2초이므로 넉넉하다.

 

물론, 전체 경우의 수를 다 따져보면 안된다. 

 

길이가 n 인 문자열으로 만들 수 있는 가능한 문자열의 개수를 구하는 것은 순열으로 접근가능하며, 시간 복잡도는 O(N!) 이다. 그리고 n 의 최대는 50 이다. 그러므로 모든 경우의 수를 다 따져보는 것은 불가능하다.

 

그러면 어떻게 하면 좋을까?

 

2 가지 풀이가 존재할 것 같다.

---

일단, 생각해보면 주어진 문자열로 팰린드롬을 만들 수 있는지 아닌지는

 

각각의 알파벳의 빈도를 계산하는 단계에서

 

홀수 개인 알파벳이 몇 개 인지가 중요하다.

 

홀수 개인 알파벳이 1 개보다 많다면, 그 문자열으로는 절대로 팰린드롬을 만들어낼 수 없다.

 

"가장 사전 순으로 앞선 알파벳을 먼저 사용하기"  라고 할 수 있겠다.

 

예를 들어,

AABBZZC

라는 입력이 주어진다면

 

배열이나 해쉬맵 등에 알파벳의 빈도를 저장한다. 

A	B	Z	C
2	2	2	1

그리고 가장 사전 순으로 앞서도록 팰린드롬을 만든다.

 

이를 위해서, 위와 같이 빈도를 저장한 테이블을

 

A	B	C	Z
2	2	1	2

와 같이 사전순으로 정렬된 상태에서 생각해야 한다.

 

(사실 이 부분은 배열로 빈도를 저장하면 자연스럽게 해결되는 문제이다.)

 

그리고 나서 A->B->C->Z 순으로 순회하면서

 

각각의 알파벳 빈도가 2 이상이라면

 

Output 의 앞 뒤에 해당 문자를 넣어준다. 

 

이때 중요한 것은 예를 들어 A 의 알파벳 빈도가 7 이라면,

 

AAA____AAA  와 같이 하는게 최적임에 주의한다.

 

if 문을 사용하면 AB___BA 이런 식으로 만들어 질 것이다.

 

이런식으로 빈도 테이블을 1 회 순회하고 나면

 

output 문자열은 ABC_CBA 와 같을 것이고

 

빈도 테이블은 아래와 같을 것이다.

A	B	C	Z
0	0	1	0

생각해보면 이 시점에서의 빈도 테이블은 값이 항상 0 또는 1 이라는 것을 알 수 있다.

 

이제 다시 A->B->C->Z 순으로 순회하면서

 

저장된 값이 1 이면, 넣어야 할 자리에 해당 문자열을 넣어준다.

 

위 과정을 거치면

 

팰린드롬 문자열이 만들어진다.

 

이제 출력하면 된다!

 

코드는 아래와 같다.

 

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stk;

        String input = br.readLine();
        int n = input.length();
        int[] f = new int[26];
        ArrayList<Character> list = new ArrayList<>();
        for (int i = 0; i < input.length(); i++) {
            f[input.charAt(i) - 'A']++;
            if (!list.contains(input.charAt(i))) {
                list.add(input.charAt(i));
            }
        }
        int odd = 0;
        for (int i = 0; i < 26; i++) {
            if (f[i] % 2 == 1) {
                odd++;
            }
        }
        if (odd > 1) {
            bw.write("I'm Sorry Hansoo");
        } else {
            list.sort(Character::compareTo);
            char[] output = new char[n];
            int left = 0;
            int right = input.length() - 1;
            for (int i = 0; i < list.size(); i++) {
                char nowChar = list.get(i);
                while (f[nowChar - 'A'] >= 2) {
                    output[left++] = nowChar;
                    output[right--] = nowChar;
                    f[nowChar - 'A'] -= 2;
                }
            }
            for (int i = 0; i < list.size(); i++) {
                char nowChar = list.get(i);
                if (f[nowChar - 'A'] > 0) {
                    output[left++] = nowChar;
                    f[nowChar - 'A']--;
                }
            }
            for (int i = 0; i < output.length; i++) {
                bw.write(output[i]);
            }
        }
        bw.flush();
        bw.close();
    }
}

 

---

두 번째 풀이는 보다 구현이 간단하다.

 

팰린드롬을 만들 수 있는지 여부는 첫 번째 풀이와 동일하다.

 

팰린드롬을 만드는 과정이 조금 다르다.

 

팰린드롬 문자열의 구성을 front + mid + end 단위로 쪼개서 생각하자.

 

예를 들어, AABBZ 라는 문자열이 주어지면

 

front 는 AB

 

mid 는 Z

 

end 는 BA 가 되야 할 것이다.

 

최종적인 팰린드롬은 front + mid + end 이다.

 

end 는 front 를 reverse 해서 얻을 수 있으므로, front 와 mid 만 구해내면 된다.

 

간단하다.

 

일단 빈도를 저장한 테이블을 사전 순으로 순회한다.

 

현재 바라보고 있는 문자의 빈도의 1/2 만큼 front 에 append 한다.

 

그러면 front 문자열은 완성된다.

 

mid 문자열은

 

현재 바라보고 있는 문자의 빈도가 홀수이면 mid 에 append 하여 만들어 낼 수 있다.

 

end 문자열은 front 문자열을 뒤집으면 된다.

 

위 과정을 거친 후,

 

front + mid + end 를 출력하면 된다!

 

이렇게 쪼개서 생각하는 관점이 구현이 더 간단하다. 😊

 

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stk;

        String input = br.readLine();
        int n = input.length();
        int[] f = new int[26];
        for (int i = 0; i < n; i++) {
            f[input.charAt(i) - 'A']++;
        }
        int odd = 0;
        for (int i = 0; i < 26; i++) {
            if (f[i] % 2 == 1) {
                odd++;
            }
        }
        if (odd > 1) {
            bw.write("I'm Sorry Hansoo");
        } else {
            StringBuilder front = new StringBuilder();
            StringBuilder mid = new StringBuilder();
            for (int i = 0; i < 26; i++) {
                for (int j = 0; j < f[i] / 2; j++) {
                    front.append((char) ('A' + i));
                }
            }
            for(int i = 0 ; i< 26 ; i++){
                if(f[i]%2==1){
                    mid.append((char) ('A' + i));
                }
            }
            String output = front.toString() + mid.toString() + front.reverse();
            bw.write(output);
        }

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