1213번: 팰린드롬 만들기

문제

임한수와 임문빈은 서로 알파벳 대문자로만 이루어진 영어 이름을 팰린드롬으로 바꾸는 프로그램을 만들고자 합니다. 팰린드롬이란 앞으로 읽으나 뒤로 읽으나 똑같은 문자열을 말합니다. 주어진 영어 이름의 알파벳 순서를 적절히 바꿔서 팰린드롬을 만들되, 정답이 여러 개일 경우 사전순으로 가장 앞서는 것을 출력해야 합니다. 만약 팰린드롬으로 바꿀 수 없다면 "I'm Sorry Hansoo"를 출력합니다.

• 입력: 첫째 줄에 영어 이름이 주어집니다. (알파벳 대문자로만 이루어져 있으며, 최대 50글자)
• 출력: 첫째 줄에 문제의 정답을 출력합니다.

링크: https://www.acmicpc.net/problem/1213

풀이 1: 양끝 동시 삽입 (insert 활용)

알파벳 빈도수를 구한 뒤, 역순으로 탐색하며 StringBuilder의 양 끝에 문자를 동시에 삽입하여 팰린드롬을 완성하는 직관적인 방법입니다.

1. 팰린드롬 가능 여부 판별: 홀수 번 등장하는 문자가 2개 이상 발견된다면 팰린드롬을 만들 수 없으므로 즉시 "I'm Sorry Hansoo"를 출력하고 종료합니다.
2. 중앙 문자 배치: 홀수 번 등장하는 문자가 딱 1개 있다면, 그 문자 하나를 팰린드롬의 가장 정중앙에 배치하기 위해 StringBuilder에 가장 먼저 넣어두고 카운트를 1 감소시킵니다.
3. 사전순 팰린드롬 조립: 알파벳을 역순('Z'부터 'A')으로 순회하며 StringBuilder의 맨 앞(insert(0, ...))과 맨 뒤(append(...))에 문자를 동시에 붙여 나갑니다. 역순으로 순회하기 때문에 나중에 처리되는 작은 알파벳일수록 가장 바깥쪽에 배치되어 자연스럽게 사전순으로 가장 빠른 팰린드롬이 완성됩니다.

코드 1

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));

       String s = br.readLine();
       int[] cnt = new int[26];
       
       // 알파벳 대문자 빈도수 카운트
       for (char c : s.toCharArray()) {
          cnt[c - 'A']++;
       }

       boolean flag = false;
       StringBuilder sb = new StringBuilder();
       
       // 홀수 개수인 문자 체크 및 중앙 배치
       for (int i = 0; i < 26; i++) {
          if (cnt[i] % 2 == 1) {
             // 홀수 개인 문자가 2개 이상이면 팰린드롬 불가
             if (flag) {
                bw.write("I'm Sorry Hansoo");
                bw.flush();
                return;
             }

             // 홀수 문자를 중앙에 먼저 배치하고 카운트 1 감소
             sb.append((char)(i + 'A'));
             cnt[i]--;
             flag = true;
          }
       }

       // 짝수 개수인 문자들을 팰린드롬 양끝에 대칭으로 배치
       // 사전순으로 앞서기 위해 역순('Z' -> 'A')으로 처리
       for (int i = 25; i >= 0; i--) {
          for (int j = 0; j < cnt[i] / 2; j++) {
             sb.append((char)(i + 'A'));       // 맨 뒤에 추가
             sb.insert(0, (char)(i + 'A'));    // 맨 앞에 추가
          }
       }

       bw.write(sb.toString());

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

풀이 2: 앞부분 생성 후 뒤집기 (reverse 활용)

insert(0) 연산은 기존 문자열을 모두 밀어내야 하므로 문자열이 길어질 경우 비효율적(O(N^2))일 수 있습니다. 따라서 사전순으로 앞부분 절반을 먼저 만든 뒤, 이를 뒤집어 뒷부분을 완성하는 방식(O(N))이 성능 면에서 가장 효율적입니다.

1. 팰린드롬 가능 여부 판별: 빈도수를 카운트한 후, 홀수 개인 문자가 2개 이상이라면 팰린드롬을 만들 수 없으므로 즉시 "I'm Sorry Hansoo"를 출력합니다.
2. 앞부분 생성 (사전순 정렬): 정답이 여러 개일 경우 사전순으로 가장 앞서야 하므로, 알파벳을 'A'부터 'Z'까지 순방향으로 순회합니다. 각 알파벳의 빈도수를 2로 나눈 몫만큼 StringBuilder(front)에 이어 붙입니다(append).
3. 팰린드롬 조립 (앞 + 중앙 + 뒤): 앞에서 만든 front, 홀수 개인 문자가 있었다면 그 문자 하나, 그리고 front를 역순으로 뒤집은 문자열(front.reverse())을 차례대로 이어 붙여 완벽한 팰린드롬을 완성합니다.

코드 2

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));

       String s = br.readLine();
       int[] cnt = new int[26];
       
       for (char c : s.toCharArray()) {
          cnt[c - 'A']++;
       }

       int oddCount = 0;
       char centerChar = '\0';
       
       for (int i = 0; i < 26; i++) {
          if (cnt[i] % 2 != 0) {
             oddCount++;
             centerChar = (char)(i + 'A');
          }
       }

       if (oddCount > 1) {
          bw.write("I'm Sorry Hansoo");
       } else {
          StringBuilder front = new StringBuilder();
          
          for (int i = 0; i < 26; i++) {
             for (int j = 0; j < cnt[i] / 2; j++) {
                front.append((char)(i + 'A'));
             }
          }
          
          StringBuilder ans = new StringBuilder(front);
          if (oddCount == 1) {
             ans.append(centerChar);
          }
          ans.append(front.reverse());
          
          bw.write(ans.toString());
       }

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

알고리즘 분류

문자열 처리 (String), 그리디 알고리즘 (Greedy), 구현 (Implementation)