문자열을 입력받고 팰린드롬이 가능하다면 팰린드롬으로 만든 문자열을, 불가능하다면 "I'm Sorry Hansoo"를 출력하는 문제이다.

문제를 잘 이해하는 것이 가장 중요하다. 특히 2가지 핵심 사항을 파악해야한다.

1. 언제 팰린드롬이 가능하고 언제 팰린드롬이 불가능할까?

홀수 번 등장한 문자의 개수가 2개 이상이면 팰린드롬이 불가능하고, 그렇지않으면 팰린드롬이 가능하다.

2.팰린 드롬이 가능한 경우 -> 팰린드롬을 만드는 패턴이 전부 동일할까?

팰린 드롬이 가능한 경우는 홀수 번 등장한 문자의 개수가 1개이거나 0개인 경우로 나뉜다.

전자의 경우는 -> 아스키코드 역순으로 중간에서부터 앞,뒤로 계속 붙여나가면되고,
후자의 경우는 -> 아스키코드 역순으로 중간에서부터 앞,뒤로 계속 붙여나가고 -> 마지막에 홀수 번 등장한 문자를 중간에 삽입해줘야한다.

3. 풀이 1

#include <bits/stdc++.h>

using namespace std;
map <char, int> mp;
int main() {
    string s,res;
    char odd_char;
    int odd_cnt=0;
    cin >> s;
    for(char c:s) { //O(L*logM)
        mp[c]++; //{'A', 3},{'B', 2}
    }
    for(auto it:mp) { // O(M)
        if(it.second % 2 != 0) {
            odd_cnt++;
            odd_char = it.first;
        }
        if(odd_cnt >= 2) {
            cout << "I'm Sorry Hansoo";
            exit(0);
        }
    }
    for(auto it:mp) { //O(M)
        for(int i=0;i<it.second / 2; i++) {
            res += it.first;
        }
    }
    cout << res;
    if(odd_cnt == 1) cout << odd_char;
    reverse(res.begin(), res.end()); //O(L)
    cout << res;
    return 0;
}

아스키코드 오름 차순으로, 등장 횟수 /2 만큼 출력하고 -> 홀수번 등장한 문자 있으면 뒤에 출력하고 -> reverse로 뒤집어서 다시 출력하는 방식이다.

시간복잡도는 O(L*logM+2M+L) 이다.

4. 풀이 2

#include <bits/stdc++.h>

using namespace std;

int cnt[26];
int main() {
    string input, res;
    int odd_cnt=0;
    char odd_char;
    cin >> input;
    for(char c:input) {
        cnt[c-'A']++;
    }
    
    for(int i=0; i<26;i++) {
        if(cnt[i]%2!=0) {
            odd_cnt++;
            odd_char = i+'A';
            if(odd_cnt>=2) {
                cout << "I'm Sorry Hansoo";
                exit(0);
            }
        }   
    }
    
    for(int i=25;i>=0; i--) {
        for(int j=0;j<cnt[i]/2;j++) {
            res=char(i+'A')+res;
            res=res+char(i+'A');
        }
    }
    if(odd_cnt==1) res.insert(res.begin()+res.size()/2, odd_char);
    cout << res;
    
    
    return 0;
}

5. 오답노트

(1) 카운팅 배열을 빨리 캐치하자

카운팅 배열 문제임을 빠르게 캐치하지 못했다.

문자 카운팅의 경우 array로 카운팅 배열 만드는게 유리한데, 이를 캐치하지못해서 map으로 카운트하는 실수를 했다.

또, 이번에 든 생각이 문자일때 array로 카운팅 배열 만드는게 유리한 이유가 -> 반복문 사용하면 순방향, 역방향 순회가 모두 쉬워지니까 그런 것 같기도하다.

(2) str.begin() 사용법

문자 1개를 std::string에 삽입할때는

s1.begin(pos, char) 

해주면 된다. 이때 pos에는 삽입할 위치를 가리키는 이터레이터를 전달해줘야한다.

res.insert(res.begin()+res.size()/2, odd_char);

위와 같이 사용하면 된다.