[백준/BOJ] 1213번 팰린드롬 만들기 (C++)

www.acmicpc.net/problem/1213

1213번: 팰린드롬 만들기

해결하는데 해맨 구현 문제

처음에 next_permutation을 이용해 순열을 구하면서 팰린드롬을 만족하는지 확인하려했는데, 시간초과가 발생했습니다. 시간복잡도를 O(N!)이 아닌 O(N^2)으로 잘못 알고 있었습니다. 입력받은 문자열에서 알파벳이 나온 수가 홀수개이고, 그게 두개 이상 있다면 팰린드롬이 될 수 없다는 것을 이용하는 것이 포인트입니다.

 

#include <iostream>
#include <algorithm>
using namespace std;

int alpha[26];

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    string s;
    cin>>s;
    for(int i = 0; i < s.size(); i++) {
        alpha[s[i] - 'A']++;
    }
    
    int oddNum = 0;
    int midIdx = -1; // 팰린드롬 문장의 길이가 홀수개일때 사용
    
    for(int i = 0; i < 26; i++) {
        if(alpha[i] > 0 && alpha[i] % 2 == 1) {
            oddNum++;
            midIdx = i;
            alpha[i]--;
        }
    }
    
    if(oddNum > 1) {
        cout<<"I'm Sorry Hansoo";
    } else {
        string answer, tmp;
        for(int i = 0; i < 26; i++) {
            if(alpha[i] > 0) {
                for(int j = 0; j < alpha[i] / 2; j++) {
                    answer += 'A' + i;
                }
            }
        }
        
        tmp = answer;
        reverse(tmp.begin(), tmp.end());
        if(midIdx != -1) answer += 'A' + midIdx;
        answer += tmp;
        
        cout<<answer;
    }
}