백준 1213

백준 1213 : 팰린드롬 만들기

1. 알파벳 별로 개수 세기
2. 홀수가 2개 이상이면 불가능
3. 홀수가 1개면 가운데 홀수인 알파벳을 넣으면 됨
4. 팰린드롬은 우선 갯수의 절반만큼 넣고, 나머지는 reverse해서 이어붙임

정답 코드

#include <iostream>
#include <algorithm>

using namespace std;

string s;
int len; //size of string (0~50)
int cnt[26];
string ans;

int main() {
	cin>>s;
	len = s.length();
	
	//count alphabets (0~26)
	for(int i=0; i<len; i++) {
		cnt[s[i]-'A']++;
	}
	
	//count odds
	int numOdd=0;
	string mid; //char with odd num
	for(int i=0; i<26; i++) {
		if(cnt[i]%2 == 1) {
			numOdd++;
			mid=char('A'+i);
		}
	}
	
	
	if(numOdd>1) { //impossible
		cout<<"I'm Sorry Hansoo"<<"\n";
		return 0;
	}
	
	//make palindromes
	for(int i=0; i<26; i++) {
		if(cnt[i]==0) {
			continue;
		}
		
		for(int j=0; j<cnt[i]/2; j++){
			ans+=char('A'+i);
		}
	}
	
	//assemble 
	string temp = ans;
	reverse(temp.begin(), temp.end());
	
	if(numOdd==1) {
		ans += mid;
	}
	ans+=temp;
	
	cout<<ans<<"\n";	
	
	return 0;
}

다른 버전

#include<bits/stdc++.h> 
using namespace std; 
string s, ret; 
int cnt[200], flag; 
char mid;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> s;
	for(char a : s)cnt[a]++;
	for(int i = 'Z'; i >= 'A'; i--){
		if(cnt[i]){
			if(cnt[i] & 1){
				mid = char(i);flag++;
				cnt[i]--;
			}
			if(flag == 2)break;
			for(int j = 0; j < cnt[i]; j += 2){
				ret = char(i) + ret; 
				ret += char(i);
			}
		}
	}
	if(mid)ret.insert(ret.begin() + ret.size() / 2, mid);
	if(flag == 2)cout << "I'm Sorry Hansoo\n";
	else cout << ret << "\n"; 
}

앞의 코드와 다른 점

1. char (a: s) 를 이용해서 string 길이만큼 cnt[(알파벳)] 위치에서 count
2. 팰린드롬을 만들 때 맨 앞과 맨 뒤에 하나씩 넣어가며 팰린드롬 생성
3. 먼저 팰린드롬을 만들어놓고 맨 마지막에 insert 함수를 이용해 중간에 삽입