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

1213번: 팰린드롬 만들기

 

boj.kr

풀이

문자열을 입력받은 뒤, 각 알파벳의 개수를 세어준다. 만약 모든 알파벳의 갯수가 짝수라면 팰린드롬이 가능하다. 하지만 알파벳의 갯수가 홀수일 경우가 2개 이상이라면 팰린드롬을 만들 수 없다. 그 외의 경우에는 모두 팰린드롬을 만들 수 있다.

정답은 사전 순서 중 가장 앞 순서에 오는 것이다. 사전 상 가장 앞에 오는 팰린드롬은 어렵지 않게 구할 수 있다. 이 경우는 갯수가 홀 수인 알파벳이 있을 때와 없을 때로 나뉘는데, 모든 알파벳의 갯수가 짝수인 경우는 'A' 부터 'Z' 순서로 미리 세어 둔 알파벳 갯수의 절반 만큼을 사용해서 문자열을 만들고, 해당 문자열을 뒤집은 문자열과 함께 출력해주면 된다. 그리고 한 개의 알파벳이 홀 수인 경우는 그 알파벳을 문자열과 뒤집은 문자열 사이에 넣어서 출력하면 된다.

코드

C++

	#include <iostream>
	#include <algorithm>
	using namespace std;
	string name;
	int alpha[26];
	int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> name;
	for (char c : name)
	alpha[c - 'A']++;
	int odd_cnt = 0;
	bool is_possible = true;
	for (int i = 0; i < 26; i++) {
	if (alpha[i] % 2 == 1) odd_cnt++;
	if (odd_cnt > 1) {
	is_possible = false;
	break;
	}
	}
	if(!is_possible) cout << "I'm Sorry Hansoo\n";
	else {
	string ans = "";
	char odd = 'a';
	for (int i = 0; i < 26; i++) {
	for (int j = 0; j < alpha[i] / 2; j++)
	ans += (char)(i + 'A');
	if (alpha[i] % 2 == 1) odd = i + 'A';
	}
	string rev = ans;
	reverse(rev.begin(), rev.end());
	if (odd == 'a') cout << ans + rev << '\n';
	else cout << ans + odd + rev << '\n';
	}
	return 0;
	}

view raw 1213.cpp hosted with ❤ by GitHub