1. 문제 접근

• 먼저 팰린드롬 가능/불가능 여부를 check하고
• 팰린드롬이 가능하다면, 문자열 처리를 통해 팰린드롬을 만든다.
  • 이때, 홀수개의 문자열을 제대로 처리해야 한다.

---

2. 시행착오

1. 여러 개의 출력이 나올 수 있는 팰린드롬 중 사전순서대로 가장 앞선 팰린드롬을 제작해야 하기 때문에 홀수개의 sub문자열을 처리하는 데 고민을 함

---

3. 코드 및 풀이

3.1 풀이

• 내가 처음으로 푼 방법은 다음과 같다.

• 우선 들어오는 문자열을 map자료구조를 통해 해결

  • key는 문자열
  • value는 문자열 개수

• 우선 문자열 길이가 짝수인 케이스, 홀수인 케이스로 나누어서 팰린드롬 여부를 판단

  • 문자열 길이 짝수 : 홀수 개의 문자가 존재하면 무조건 못 만듦(ex. ABAA)
  • 문자열 길이 홀수 : 오직 문자 한 종류만 홀수 개이면 상관없음(ex. AABBB => ABBBA)
  • 문자열 길이가 홀수인 경우이면서, 문자 한 종류만 홀수 개인 경우에, tmp 변수에 해당 문자열을 할당함

• 팰린드롬을 만드는 과정은 다음과 같음

  • map 자료구조는 ordered하게 저장
    => 따라서 이터레이터를 달면서 원소를 탐색할 때는 무조건 key가 알파벳 오름차순으로 정렬된 상태에서 출력(for (auto it : mp) 코드)
    => 이 점 때문에 해당 코드로 만들어지는 팰린드롬은 무조건 사전순으로 정렬할 때 가장 먼저 오는 것을 보장
  • 이때 안쪽 for문을 통해 tmp 변수를 기점으로 tmp 앞에 문자열을 붙일front와 뒤에 문자열을 붙일 back 변수에 반복문을 통해서 문자열을 할당
  • 그리고 reverse()를 통해 back의 문자열을 뒤집음
  • ex) case : AABBB => {'A' : 2, 'B' : 3}에 저장
    => front엔 AB tmp엔 A, back엔 AB
    => reverse()를 통해 back 뒤집음 => BA
    => 각각을 concat하면 ABABA라는 팰린드롬이 만들어짐

#include<bits/stdc++.h>
#include <bits/stdc++.h>
using namespace std;

int len, cnt;
string s;
map<char, int> mp;
string front, tmp, back;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    // 1. Input string and str to map(char type)
    cin >> s;
    len = s.length();
    for(char c : s) mp[c]++;
    
    // 2. Check If it's impossible to make palindrome
    // 2.1 If size is even number
    if (len % 2 == 0) {
        for (auto it : mp){
            if (it.second % 2 != 0) {
                cout << "I'm Sorry Hansoo";
                exit(0);
            }
        }
    }
    // 2.2 If size is odd number
    else {
        for (auto it : mp) {
            if (it.second % 2 != 0 ) {
                tmp += it.first;
                cnt++;
            }
            if (cnt > 1) {
                cout << "I'm Sorry Hansoo";
                exit(0);
            }
        }
    }
    
    // 3. Make palindrome
    for(auto it : mp){
        for(int i = 0; i < it.second / 2; i++) {
            front += it.first;
            back += it.first;
        }
    }
    reverse(back.begin(), back.end());
    cout << front + tmp + back;
}

3.2 개선된 방법

• 첫 번째 방법에서 간과한 것은
  • 1. 개개의 문자를 다루기 때문에 map이 아닌 array로 써도 문제 없다는 점
  • 2. 입력 문자열의 길이가 짝수인지, 홀수인지 구별 안하고 flag변수를 통해서 처리할 수 있다는 점이다.
       - flag변수는 해당 문자의 개수가 홀수 개이면 1씩 count되는 것인데, 홀수 개의 문자가 2 이상이면 무조건 팰린드롬을 제작하지 못하게 된다.(굳이 짝/홀 나누지 않아도 무관
       - 이 과정에서 첫 번째 방법에서 했던 것과 비슷하게 mid 변수에 홀수개 문자일 경우, 그 문자를 추가하는 방식을 그대로 사용
  • 3. 그리고 array을 순회하는 과정에서 ret변수를 활용해서 팰린드롬을 만들고, 마지막에 mid문자열을 insert()하는 방식으로 해결한다.

#include <bits/stdc++.h>
using namespace std;

string s, ret;
// 0. character => use array!
int cnt[200], flag;
char mid;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    // 1. Input string and str to array
    cin >> s;
    for(char c : s) cnt[c]++;

    // 2. Traverse array if there is odd number
    for(int i = 'Z'; i >= 'A'; i--) {
        if(cnt[i]) {
            if(cnt[i] & 1){
                mid = char(i);
                flag++;
                cnt[i]--;
            }
            // 2.1 if flag 2 => impossible case
            if(flag == 2) break;
            // 2.2 after checking, characters in array are added to ret
            for(int j = 0; j < cnt[i]; j += 2){
                ret = char(i) + ret;
                ret += char(i);
            }
        } 
    }
    
    // 3. mid to ret
    if(mid) ret.insert(ret.begin() + ret.size() / 2, mid);
    if(flag == 2) cout << "I'm Sorry Hansoo\n";
    else cout << ret << "\n";
}

---

Reference