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

문제 : 팰린드롬 만들기

유형 : 문자열, 그리디

문제 해석

• 주어진 문자열로 팰린드롬을 만들 수 있으면 사전 순으로 가장 앞에 있는 팰린드롬을 만든다.
• 팰린드롬을 만들 수 없으면 I'm Sorry Hansoo를 출력한다.

해결 전략

• A~Z 각 알파벳의 개수 중 홀수인 개수가 1개보다 많은 경우 팰린드롬을 만들 수 없다.

설계, 구현

• 팰린드롬을 만들 수 있는 경우

  • A~Z 각 알파벳의 개수 중 홀수는 최대 1개다. 즉 홀수인 알파벳 한개를 answer 문자열 중간에 놓고 시작한다. answer[size/2] = i + 'A';
  • 우리는 앞서 알파벳의 개수가 홀수인 경우 홀수 알파벳 하나를 answer 중간에 놓고 시작했기 때문에 각 알파벳이 존재한다면 그 알파벳은 무조건 짝수개 이다. answer의 맨 앞과 맨뒤에서 부터 A~Z(0~26) 순으로 남은 알파벳 개수만큼 넣어 주면 팰린드롬이 되면서 동시에 사전순이다.

• 팰린드롬을 만들 수 없는 경우

  • I'm Sorry Hansoo를 출력한다.

주의할 점

string answer를 char answer[50]로 변경

• string answer를 선언 하고, 크기가 정해지지 않은 문자열 배열에 answer[size/2] = i + 'A';를 선언해서 런타임 에러 (Segfault)가 발생했다. string answer를 char answer[50]으로 바꿨다. 50은 최대글자다.

코드

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

int alpha[26];
char answer[50];

void solve(int odd_cnt, int size) {
	if(odd_cnt > 1) {
		cout << "I'm Sorry Hansoo";
		return;
	} else {
		int l=0, r=size-1;
		for(int i=0; i<26; i++) {
			while(alpha[i] > 1) {
				answer[l++] = i + 'A';
				answer[r--] = i + 'A';
				alpha[i] -= 2;
			}
		}
		
		for(int i=0; i<size; i++) {
			cout << answer[i];
		}
	}
}

int main() {
	string s;
	cin >> s;
	int size = s.size();
	for(int i=0; i<size; i++) {
		alpha[s[i]-'A']++;
	}
	
	int odd_cnt = 0;
	for(int i=0; i<26; i++) {
		if(alpha[i]%2 == 1) {
			odd_cnt++;
			answer[size/2] = i + 'A';
			alpha[i+'A']--;
		}
	}
	
	solve(odd_cnt, size); 
	return 0;
}