BOJ 1213번 팰린드롬 만들기

BOJ : https://www.acmicpc.net/problem/1213

github : https://github.com/junho0956/Algorithm/tree/master/1213

 

알파벳이 A-Z 까지 주어진다.

이 때 string 의 각 문자열을 [26] 배열을 통해 그 갯수를 저장해놓을 수 있다.

문제의 조건에서는 정렬을 통한 앞선 팰린드롬을 출력하라고 했으니, [26]배열을 통해 순서대로 만들면 된다.

 

주어진 문자열이 홀수일수도 있고, 짝수일수도 있다.

결국 팰린드롬을 만들지 못하는 경우는 홀수이건, 짝수이건 간에 그 경우가 2번이상 나타날때이다.

이때를 제외하고는 무조건 팰린드롬을 만들 수 있다.

 

팰린드롬을 만들것이므로, 미리 앞의 반만 만들어 놓으면 그 뒤의 반은 앞의 것을 반대로 출력해주기만 하면된다.

결국 AA.. 에서 A는 2번 나왔으므로 반만 만들어놓는 스트링에는 A가 1번 입력될 것이다.

AAA..이면 당연히 1번만 입력된다.

그러므로 [26] 배열의 값을 통째로 가지고 있다가 /2 만큼 스트링에 포함시켜주면 된다.

 

문자열이 홀수가 나오는 경우, 그 값을 미리 저장해두면

반을 만들어놓고 이 값을 판단하여 만들어놓은 문자열에 추가시켜주기만 하면 문제없다.

 

#include <iostream>
#include <string>
#include <vector>
using namespace std;
 
int use[26];
 
int main() {
    vector<pair<char, int> > v;
    string str;
    int mid = -1;
    bool flag = false;
 
    cin >> str;
    for (int i = 0; i < str.size(); i++) use[str[i] - 'A']++;
 
    for (int i = 0; i < 26; i++) {
        if (use[i] % 2 && flag) {
            cout << "I'm Sorry Hansoo";
            return 0;
        }
        else if (use[i] % 2) {
            flag = true;
            mid = i;
            v.push_back({ i + 'A', use[i] });
        }
        else v.push_back({ i + 'A', use[i] });
    }
 
    string ans = "";
    for (int i = 0; i < v.size(); i++)
        for (int k = 0; k < v[i].second / 2; k++)
            ans += v[i].first, cout << v[i].first;
 
    if (mid != -1) ans += mid + 'A';
    for (int i = ans.size() - 1; i >= 0; i--)
        cout << ans[i];
 
    return 0;
}