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

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

 

우선 홀수개인 알파벳의 개수가 2개 이상이면 팰린드롬을 만들 수 없기 때문에 이 경우에는 바로 "I'm Sorry Hansoo" 를 출력한다.

 

그리고 홀수개인 알파벳의 개수가 한개라면 이 경우에서는 알파벳이 n/2 , 1, n/2 로 나눠지고

나머지의 경우에는 알파벳이 n/2, n/2 로 나눠진다.

 

사전순서대로 저장해주는 map<char, int> 를 이용해 알파벳들을 저장하고 순회하면서 n/2만큼을 출력할 문자열에 붙여주고 남은 n/2는 스택에 넣어둔다. 그리고 홀수개인 알파벳이 하나가 있다면 n/2, 1, n/2의 중간의 1개의 알파벳을 저장해둔다. 

홀수개인 알파벳이 있었다면 저장해둔 1개의 알파벳을 붙여두고 스택에서 빼가면서 출력할 문자열에 붙여준다.

 

ex) AABBCCCCC - A : 2개, B : 2개, C : 5개 - 홀수개인 알파벳이 C 하나이기 때문에 팰린드롬을 만들 수 있다.

AA : A, A로 나눠짐

BB : B, B로 나눠짐

CCCCC : CC , C, CC 로 나눠짐

map에 저장 : A : 2, B : 2, C : 5

출력 문자열 : ""

A 순회 -> 출력 문자열 : "A" , 스택 : (1, A)

B 순회 -> 출력 문자열 : "AB", 스택 : (1, A), (1, B)

C 순회 -> 출력 문자열 : "ABCC", 스택 : (1, A), (1, B), (2, C) , 저장할 알파벳 : C

홀수개인 알파벳이 있으므로 저장해둔 알파벳이 존재한다. -> 출력 문자열 : "ABCCC"

스택 순회 -> (2, C) -> 출력 문자열 : "ABCCCCC"

스택 순회 -> (1, B) -> 출력 문자열 : "ABCCCCCB"

스택 순회 -> (1, A) -> 출력 문자열 : "ABCCCCCBA"

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>

using namespace std;
using ll = long long;

void PushStr(string& str, char c, int cnt) {
	for (int i = 0; i < cnt; i++) {
		str += c;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	map<char, int>mp;
	string str;
	cin >> str;
	for (int i = 0; i < str.length(); i++) {
		mp[str[i]]++;
	}
	int oddCnt = 0;
	for (auto a : mp) {
		if (a.second % 2 == 1) oddCnt++;
	}
	if (oddCnt > 1) {
		cout << "I'm Sorry Hansoo";
	}
	else {
		string ans = "";
		stack<pair<char, int>> st;
		char c;
		for (auto a : mp) {
			if (a.second % 2 == 1) c = a.first;
			PushStr(ans, a.first, a.second / 2);
			st.push({ a.first,a.second / 2 });
		}
		if (oddCnt == 1) ans += c;
		while (!st.empty()) {
			auto top = st.top();
			st.pop();
			PushStr(ans, top.first, top.second);
		}
		cout << ans;
	}
};