[백준 c++] 1213 팰린드롬 만들기

문제 설명

https://www.acmicpc.net/problem/1213
알파벳 대문자로만 이루어진 문자열이 팰림드롬으로 바꿀 수 있는지 판별하고, 바꿀 수 있다면 사전 순 팰린드롬 문자열로 바꿔 출력하는 문제다.

아이디어

1. map<string, int> 을 이용하여 입력받은 문자열이 각각 몇개인지 저장한다

map<string, int> p;
int main() {
	cin >> s;
	for (int i = 0; i < s.size(); i++) {
		k = s[i];
		p[k] += 1;
	}
    

2. 팰린드롬은 홀수인 문자의 개수가 2개 이상이면 불가능하다.
   문자 개수가 홀수면 arr에 차곡 차곡 저장한다. (나중에 가운데에 몰아서 출력하기 위해)
   문자 개수가 짝수면 cnt++

	for (auto c : p) {
		if (c.second % 2==1) {
			arr[l] = c.first;
			l++;
		}
		cnt +=c.second / 2;
		
	}
    

3. 문자열 res에 각각 문자 개수의 절반씩 append

	if (cnt < (s.size() / 2)) {
		cout << "I'm Sorry Hansoo";
	}
    
	else {
		for (auto c : p) {
			for (int i = 0; i < c.second / 2; i++) {
				res += c.first;
			}
		}
        

4. 원본은 res1에 저장하고 문자열 res를 뒤집는다. arr에 저장해뒀던거 하나씩 출력하고 res1+=res을 한다.

		res1 = res;
		reverse(res.begin(), res.end());
		for (int i = 0; i < l; i++) {
			res1 += arr[i];
		}
		res1 += res;
		cout << res1;
        

---

전체 코드

#include <iostream>
#include <algorithm>
#include<string>
#include <string.h>
#include <map>
using namespace std;

string s,k,res,res1;
int cnt,l;
map<string, int> p;
string arr[26];

int main() {
	cin >> s;
	for (int i = 0; i < s.size(); i++) {
		k = s[i];
		p[k] += 1;
	}
    
	for (auto c : p) {
		if (c.second % 2==1) {
			arr[l] = c.first;
			l++;
		}
		cnt +=c.second / 2;
		
	}
    
	if (cnt < (s.size() / 2)) {
		cout << "I'm Sorry Hansoo";
	}
    
	else {
		for (auto c : p) {
			for (int i = 0; i < c.second / 2; i++) {
				res += c.first;
			}
		}
		res1 = res;
		reverse(res.begin(), res.end());
		for (int i = 0; i < l; i++) {
			res1 += arr[i];
		}
		res1 += res;
		cout << res1;

	}
}