[알고리즘/문제] 백준 1213번: 팰린드롬 만들기

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

1213번: 팰린드롬 만들기

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

int cnt[26], odd, cntNum;
string s, ret, temp, center;
map<char, int> mp;

int main() {
	cin >> s;
	for (char c : s) {
		cnt[c - 'A']++;
	}
	/*
	for (int i = 0; i < 26; i++) {
		if (cnt[i] +'A' && !mp['A' + i] {
			mp['A' + i] = cnt[i] +'A';
		}
	}
	*/

	for (int i : cnt) {
		if (i % 2 != 0) odd++;
	}

	if (odd > 1) cout << "I'm Sorry Hansoo" << '\n';
	else {
		for (int i = 25; i >= 0; i--) {
			cntNum = 0;
//			cout << "[1] i" << '\n';
			while (cnt[i] && cnt[i]/2 != cntNum) {
//				cout << "[2]" << i << '\n';
				ret = char(i+'A') + ret;
				ret += char(i + 'A');
				cntNum++;
			}
			if (cnt[i] % 2 != 0) {
//				cout << "[3]" << i << '\n';
				center = i+'A';
			}
			
		}
		ret.insert(ret.length()/2, center);
		cout << ret << '\n';
	}


	return 0;
}

이 문제 1시간 30분동안이나 풀었다..

입력받은 글자를 팬린드롬으로 만드는 문제였다.

팬린드롬으로 안되는 조건이면 다른 문자열을 출력한다.

 

우선 팬린드롬이 안되는 조건이 무엇인지 부터 생각해봤다.

개수가 홀수개인 알파벳이 2개이상 이면 만들어지지 않았다.

예를들어 AAABBB는 팬린드롬이 만들어지지 않는다.

 

위 코드에서는 odd가 1이상인 경우는 문자열을 출력하도록 했다.

가능한 경우에 만드는 방법도 생각해야했다.

처음에는 A부터 차례대로 개수의 절반만 채우고 reverse()를 통해 뒤에 붙이는 식의 코드를 썼다.

 

그런데 반례가 있었는지 1%에서 틀렸습니다가 떴다.

반례가 뭔지 아직도 모른다..

 

다음은 큰돌님이 작성한 코드인데, 이걸 참고해서 다시 짰다.

역시 깔끔하다...

#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. 대칭이 되는 문자열을 만들때 앞뒤를 붙여주며 만든다.

2. 오름차순으로 만들기 위해 역순으로 가운데부터 생성한다.

3. &1 비트연산으로 홀수 판별가능하다. (짝수는 !( &1))

 

[인프런 강의]

https://inf.run/QKBXL

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트 강의 - 인프런