[백준][문자열] 1213 팰린드롬 만들기 c++ 구현

목차

 

 

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

문제

 

문제 구현 방향

50!이라는 모든 문자열을 만들고 하기에는 수가 너무 커서 초과가 난다..

따라서 문자를 따로 저장해 놓고 직접 문자열을 만족하게 만들어 주어야 한다.

 

 

map에 대한 설명 참고

https://be-senior-developer.tistory.com/18

[이진트리] map, set c++ 구현

 

 

코드 구현

#include <iostream>
#include <vector>
#include<map>
#include<algorithm>

using namespace std;

map<char, int>m;

int main(){
    int cnt = 0, odd=0;
	string str;
    char ans[100];  //최종 문자열
	cin >> str;
    for (int i = 0; i < str.length(); i++) {
        if (!m[str[i]]) {  //문자열이 없었을 경우
            m[str[i]] = 1;
        }
        else {
            m[str[i]]++;  //있었다면 1++
        }
    }

    for (auto k = m.begin(); k != m.end(); k++) {
        if (k->second % 2 != 0)
            odd++;
        if (odd > 1) {  //홀수개가 2개이상일 경우 팰린드롬x
            cout << "I'm Sorry Hansoo";
            return 0;
        }
        while (k->second > 1) { //1개 이하가 될때까지 앞 뒤로 추가
            ans[str.size() - 1 - cnt] = k->first;
            ans[cnt] = k->first;
            cnt++;
            k->second -= 2;
        }
    }
    for (auto k = m.begin(); k != m.end(); k++) {  //홀수개였다면 아직 남아있음
        if (k->second == 1)
            ans[str.size() / 2] = k->first;  //가운데에 문자열 추가
    }
    ans[str.size()] = '\0';  //끝에 종결 문자열 추가
    cout << ans;
}