BOJ_1213 : 팰린드롬 만들기

👉 문제링크

1213번: 팰린드롬 만들기

---

---

🔸 문제 분석 🔸

• 주어진 문자열을 팰린드롬으로 바꾼다. 팰린드롬은 데칼코마니 문자열이다.
• 문자열의 문자 종류 중 홀수 개가 1개만 있어야 한다.

🔸 코드 🔸

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String hansu = sc.next();
        int[] alpha = new int[26];

        for (int i = 0; i < hansu.length(); i++) {
            alpha[hansu.charAt(i) - 'A']++;
        }

        int hol_idx = -1;

        for (int i = 0; i < 26; i++) {
            if (alpha[i] % 2 != 0) {
                if (hol_idx == -1)
                    hol_idx = i;
                else {
                    System.out.println("I'm Sorry Hansoo");
                    System.exit(0);
                }
            }
        }
        
        String answer = "";

        for (int i = 0; i < 26; i++) {
            if ((i != hol_idx && alpha[i] > 0) || (i == hol_idx && alpha[i] > 2)) {
                for (int j = 0; j < alpha[i]/2; j++) {
                    answer += (char)('A' + i);
                }
                alpha[i] -= alpha[i]/2;
            }
        }

        if (hol_idx != -1) {
            alpha[hol_idx]--;
            answer += (char) ('A' + hol_idx);
        }

        for (int i = 25; i >= 0; i--) {
            if (alpha[i] > 0) {
                for (int j = 0; j < alpha[i]; j++) {
                    answer += (char)('A' + i);
                }
            }
        }

        System.out.println(answer);
    }
}

🔸 코드 해석 🔸

• 입력된 문자열의 문자들을 A~Z를 0~25로 바꿔 alpha배열에 카운트한다.
• alpha에서 홀수개 인덱스를 hol_idx에 저장한다.
  • 홀수개 인덱스가 2개 이상이면 팰린드롬이 될 수 없으므로 사과문을 출력하고 프로그램을 종료한다.
• 사전순으로 출력하라고 했으니 정답을 세 부분으로 나누어 출력한다.
  
  • 팰린드롬의 앞 부분을 만든다.
    • hol_idx가 아니면서 alpha에 값이 남았거나, hol_idx면서 2이상이면 그 절반만큼 정답에 추가한다.
    • alpha값은 2로나눈 몫으로 저장한다.
  • 팰린드롬의 중간 부분을 만든다.
    • 홀수개 인덱스가 있었다면, 정답에 추가한다.
  • 팰린드롬의 뒷 부분을 만든다.
    • 남은 alpha의 값을 순서대로 정답에 추가한다.
• 정답 문자열 answer을 출력한다.

---

 

🔸 end 🔸

• 다 풀고보니 개념은 그렇게 어렵지 않았는데, 팰린드롬을 완성할 때 앞 부분과 뒷 부분의 조건이 조금씩 다른게 힘들게했다.