백준1213 - 팰린드롬 만들기

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

1213번: 팰린드롬 만들기

입력한 문자열을 조사하여 글자 출현 횟수가 홀수인 글자가 2개 이상이면 펠린드롬을 만들지 못한다. 그 외에 경우에 글자 출현 횟수를 2로 나누어 몫을 글자 출현 횟수로 지정하고 펠린드롬 앞에 부분(펠린드롬 절반)을 생성한다. 입력한 글자의 갯수가 홀수이면 홀수인 글자를 기억해놓는다. 단 홀수인 글자의 갯수가 2개 이상이면 펠린드롬을 만들지 못한다. 펠린드롬을 완성하기 위해서 앞에 부분을 반전시켜 저장한다. 입력한 글자의 수가 짝수개이면 앞에 부분과 뒤에 부분을 더하고 입력한 글자의 수가 홀수개이면 앞에 부분을 더하고 중간에 기억해 놓은 글자를 넣은 뒤 반전시킨 부분을 더한다.

 

ex1.)AABBC

A : 2

B : 2

C : 1

펠린드롬 앞 부분 : AB

펠린드롬 중간 부분 : C

펠린드롬 뒷 부분 : AB를 반전시킨 BA

결과 : ABCBA

 

 

ex2.)ABBCEG

A : 1

B : 2

C : 1

E : 1

G : 1

글자 출현 횟수가 홀수개인 것이 2개 이상이기 때문에 펠린드롬 생성 불가

 

 

ex3.)BBCEGCEGGG

B : 2

C : 2

E : 2

G : 4

펠린드롬 앞 부분 : BCEGG

펠린드롬 중간 부분 : 없음

펠린드롬 뒷 부분 : BCEGG를 반전시킨 GGECB

결과 : BCEGGGGECB

 

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

string s; //입력한 문자열
string ans; //답으로 출력할 문자열
string add; //뒤에 이어붙일 문자열
map<char, int> mp; //글자들의 출현 횟수
int odd = 0; //글자의 출현 횟수 중 홀수인 수를 판단할 변수
int mat[26]; //A ~ Z까지 글자의 출현횟수를 저장할 공간
char center = NULL; //입력한 문자열의 길이가 홀수일 때 펠린드롬 생성 시 가운데 글자

int main() {
	cin >> s; //원하는 문자열 삽입

	//S를 이루는 글자들을 map을 사용하여 출현 횟수를 센다.
	for (int i = 0; i < s.size(); i++) {
		if (mp.find(s[i]) == mp.end()) {
			mp[s[i]] = 1;
		}
		else {
			mp[s[i]]++;
		}
	}

	//출현 횟수가 소수인 수들을 찾는다.
	map<char, int>::iterator iter;
	for (iter = mp.begin(); iter != mp.end(); iter++) {
		int check = iter->second;
		if (check % 2 == 1) {
			odd++;
		}
	}

	//출현 횟수가 소수인 글자가 2개 이상이면 펠린드롬을 못 만든다.
	if (odd > 1) {
		cout << "I'm Sorry Hansoo";
		return 0;
	}

	//글자들을 반복문을 통해 오름차순으로 출력하기 위하여 A ~ Z까지 출현횟수를 배열에 넣는다.
	for (int i = 0; i < 26; i++) {
		if (mp.find(char('A' + i)) != mp.end()) {
			mat[i] = mp[char('A') + i];
		}
	}
	
	
	for (int i = 0; i < 26; i++) {
		//출현횟수가 홀수인 수를 찾아서 그 글자를 가운데 글자로 설정
		if (mat[i] % 2 == 1) {
			center = char('A' + i);
		}

		mat[i] = mat[i] / 2; //(글자 출현 횟수 / 2)반복문의 기준을 생성

		for (int j = 0; j < mat[i]; j++) { //출현 횟수의 절반이 된 채로 반복문을 돌림, A ~ Z 중 오름차순으로 원소가 쌓임
			ans = ans + char('A' + i);
		}
	}

	add = ans; //뒤에 이어붙일 문자열
	
	reverse(add.begin(), add.end()); //오름 차순을 내림 차순으로 변경
	
	if (center == NULL) { //가운데 글자가 없으면 
		ans = ans + add; //뒤에 내림 차순한 문자열을 이어붙임
	}
	else { //가운데 글자가 있으면 
		ans = ans + center + add; //오름 차순한 문자열에 가운데 글자를 넣고 뒤에 내림 차순한 문자열을 이어붙임
	}

	cout << ans;
}