백준 1213 - 팰린드롬 만들기 C++

October 05, 2023

문제

백준 1213 - 팰린드롬 만들기

AAABB -> ABABA
AABB -> ABBA

접근 방식

처음에는 완전 탐색으로 해결할려나 했습니다. 그런데 시간 초과가 나와서 다시 생각해보니 문자열 순열 생성은 시간복잡도가 O(N!)로 50!은 당연히 2초를 넘는게 당연했습니다.

그래서 문제를 다시 읽어보니 여러 개의 경우 사전순으로 출력하라고 해서 문자열을 전부 만들어서 회문인지 확인하는 방식보다는 주어진 문자열에서 알파벳 개수를 세어서 회문을 만드는 방식으로 접근하기로 했습니다.

AAABB는 홀수 개수가 알파벳 A 한개라서 가능
AAABBB는 홀수 개수인 알파벳이 A, B 두개라서 회문 생성이 불가능

풀이

주어진 문자열에서 해당 대문자가 몇개 나오는지 개수를 저장
A 부터 Z까지 해당 대문자의 개수가 2 이상이면 문자열을 front 문자열에 추가하고 개수를 2만큼 뺀다. (앞뒤로 추가)
만약 문자가 1개 남는 경우, 중간에 추가

만약 이전에도 문자가 1개 발생한 경우, 회문이 될 수 없으므로 실패를 출력하고 종료한다.

front 문자열에 저장된 것들은 회문의 앞 부분이므로 뒤집은 front을 front뒤에 붙여주면 회문이 된다.

코드

string sol() {
    string input; // 주어진 문자열
    int cnt[26]; // 대문자 개수 저장할 배열
    cin >> input;

    for (char ch : input) {
        cnt[ch - 'A']++;
    }

    string front; // 회문의 앞 부분
    string middle; // 회문중 반복이 안되는 중간 부분

    bool hasAlone = false; // 회문에서 반복이 안되는 경우는 최대 1번이므로 이 정보를 저장

    for (int i = 0; i < 26; ++i) {
        while (cnt[i] >= 2) {
            front += (i + 'A');
            cnt[i] -= 2;
        }

        if (cnt[i] == 1) {
            middle = (i + 'A');
            if (hasAlone) { // 회문의 경우에는 혼자 등장하는 알파벳은 중간에 하나만 가능
                return "I'm Sorry Hansoo";
            }
            hasAlone = true;
        }
    }

    string tail = front;
    reverse(tail.begin(), tail.end());

    return front + middle + tail;
}

주어진 문자열을 한번 탐색하고 대문자의 개수를 셉니다.

다시 A부터 Z까지 반복문을 돌면서 해당 대문자의 개수가 1 이하일때까지 front에 대문자를 1개 추가하고 개수를 2 뺍니다.

해당 대문자가 홀수여서 1개가 짝이 없이 남는 경우, 회문의 가운데 부분에 추가할 수 있는지 확인해 봅니다.

만약 이전에도 남는 대문자가 있었다면 실패를 출력하고 종료합니다.

마지막으로 (front + 중간 + 뒤집은 front) 값을 출력합니다.

예시

AAABB가 주어지는 경우, A는 3개, B는 2개 입니다.

1. 초기
front : ""
middle : ""
hasAlone = false

2. 반복문, A 확인 3개 -> 1개 -> 0개
front : "A"
middle : "A"
hasAlone = true

3. 반복문, B 확인 개수 2개 -> 0개
front : "AB"
middle : "A"
hasAlone = true

4. 결과 출력
front + middle + 뒤집은 front
"AB" + "A" + "BA"
-> "ABABA"

A는 2이상이므로 front에 A를 추가하고 남은 A의 개수는 1입니다. 이때 남은 A는 1개이므로 이를 middle에 추가합니다.

B는 2개이므로 front에 B를 추가하고 반복문이 끝납니다.