[C++] 백준 1213번 : 팰린드롬 만들기

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

 

이 문제는 과거에 무척이나 헤맷던 기억이 있던 문제라 다시 풀어보고 싶었다.
그리고 잘 풀었다..ㅎㅎ

 

과거와 달라진 점이 있다면 이번엔 자료구조를 map을 사용했다는 점이다.

map은 내부적으로 '이진트리'기 때문에,
앞에서부터 차례로 탐색하면, 오름차순으로 탐색할 수 있다는 특징이 있다.
이 특징을 활용해 문제를 풀었다.

 

짠!

1. 풀이과정

1. 문자열 입력받기
2. 문자의 갯수를 저장 :
    2.1. map? ordinary map이 있나? 아니 map자체가 트리구조니까 괜찮나?
    2.2. 알파벳 배열을 만들까?
3. 정답 배열을 두개로 쪼개서
    3.1. 짝수인 문자인 경우 ansHead += (char)*(개수/2), ansTail =  (char)*(개수/2) + ansTail
    3.2. 홀수인 문자인 경우 (상동), isOdd 에 문자 저장
    3.3. isOdd에 문자가 할당되어있는데, 또 홀수 문자가 발견되는 경우 : I'm Sorry Hansoo return 0;
4. 정답 출력 : ansHead + isOdd + ansTail

 

 

2. 정답 코드

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

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    map<char, int> m;
    string str;
    cin >> str;

    for (auto &c : str)
    {
        m[c]++;
    }

    string ansHead = "", ansTail = "";
    bool prevOdd = false;
    string midChar = "";

    for (auto &ele : m)
    {
        if (prevOdd && (ele.second % 2 != 0))
        {
            cout << "I'm Sorry Hansoo";
            return 0;
        }

        ansHead += string(ele.second / 2, ele.first);
        ansTail = string(ele.second / 2, ele.first) + ansTail;

        if (ele.second % 2 != 0)
        { // 홀수인 문자인 경우
            midChar = ele.first;
            prevOdd = true;
        }
    }
    cout << ansHead << midChar << ansTail;
}

 

 

끗ㅎㅎ