[알고리즘] 1213번: 팬린드롬 만들기

 

0. 문제

 

1213번: 팰린드롬 만들기

 

문제

임한수와 임문빈은 서로 사랑하는 사이이다.

임한수는 세상에서 팰린드롬인 문자열을 너무 좋아하기 때문에, 둘의 백일을 기념해서 임문빈은 팰린드롬을 선물해주려고 한다.

임문빈은 임한수의 영어 이름으로 팰린드롬을 만들려고 하는데, 임한수의 영어 이름의 알파벳 순서를 적절히 바꿔서 팰린드롬을 만들려고 한다.

임문빈을 도와 임한수의 영어 이름을 팰린드롬으로 바꾸는 프로그램을 작성하시오.

입력

첫째 줄에 임한수의 영어 이름이 있다. 알파벳 대문자로만 된 최대 50글자이다.

출력

첫째 줄에 문제의 정답을 출력한다. 만약 불가능할 때는 "I'm Sorry Hansoo"를 출력한다. 정답이 여러 개일 경우에는 사전순으로 앞서는 것을 출력한다.

예제 입력 1

AABB

예제 출력 1

ABBA

예제 입력 2

AAABB

예제 출력 2

ABABA

예제 입력 3

ABACABA

예제 출력 3

AABCBAA

예제 입력 4

ABCD

예제 출력 4

I'm Sorry Hansoo

 

---

1. 문제 이해

 

1. 임한수의 영어 이름(문자열)을 저장한다.
2. 알파벳을 오름차순으로 정렬한다.
3. 가능한 모든 순열 가운데 팬린드롬을 찾는다. → reverse 사용하기.
4. 탐색의 순서는 사전순이다.

 

---

2. 제출

 

가. 시간 초과

// 백준 1213번: 팬린드롬
#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

string name;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> name;
	sort(name.begin(), name.end());
	do{
		string rev = name;
		reverse(rev.begin(), rev.end());
		if(rev == name){
			cout << name << "\\n";
			exit(0);
		}
	}while(next_permutation(name.begin(), name.end()));
	cout << "I'm Sorry Hansoo" << "\\n";
	return 0;
}

시간이 초과했다.

 

아마 sort로 정렬된 문자열의 경우 팬린드롬을 찾기까지 오래 걸리기 때문에 생기는 문제인 것 같다.

 

예를 들어서 입력 “ABACABA”을 정렬하면 “AAAABBC”가 된다.

 

이것을 출력 “AABCBAA”로 만들기 위해서는 많은 시간이 필요하다.

 

정렬 때문에 발생하는 불필요한 시간소모를 줄여야 한다.

 

 

나. 개선

 

시간을 줄이기 위해서 팬린드롬의 조건에 대하여 다시 이해해 보았다.

 

1) 사람들은 단어를 보면 팬린드롬인지 아닌지 대충 직관적으로 알 수 있다.

 

그 이유는 주어지는 글자들의 수를 가지고서 팬린드롬인지 알 수 있다.

 

홀수인 글자가 2개 이상인 경우 어떤 경우에도 팬린드롬이 될 수 없기 때문이다.

 

2) 사람들은 데칼코마니를 만들 수 있다.

 

사람들은 정렬된 상태에서 시작하기보다 대충의 형태를 잡고 시작하니깐 더 빠르게 팬린드롬을 만들 수 있다.

 

기계 : ABACABA → AAAABBC → AABCBAA
인간 : ABACABA → AABCBAA

 

그렇기 때문에 사전 순으로 가장 앞서는 “AAAA”를 “AA???AA”로 만들면 시간을 줄일 수 있다.

 

// 백준 1213번: 팬린드롬
#include <iostream>
#include <algorithm>
#include <map>
#include <string>

using namespace std;

string name, ret, rev, tmp;
map<char, int> mp;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> name;

	for(int i=0; i<name.length(); i++){
		mp[name[i]]++;
	}

	int cnt=0;
	for(pair<char,int> it : mp){
		if(it.second%2==1){
			cnt++;
			tmp=it.first;
		}
		if(cnt>1){
			cout << "I'm Sorry Hansoo" << "\\n";
			exit(0);
		}
		ret.append(it.second/2, it.first);
	}
	rev = ret;
	reverse(rev.begin(), rev.end());
	ret.append(tmp);
	ret.append(rev);

	cout << ret << "\\n";
	return 0;
}

 

또한 입력의 조건이 대문자 알파벳이라고 했기 때문에 map보다는 array로 푸는 방법이 더 적합한 것 같다.

 

// 백준 1213번: 팬린드롬
#include <iostream>
#include <algorithm>
#include <map>
#include <string>

using namespace std;

string name, ret, rev, tmp;
int a[26];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> name;

	for(int i=0; i<name.length(); i++){
		a[name[i] - 'A']++;
	}

	int cnt=0;
	for(int i=0; i<26; i++){
		if(!a[i]) continue;
		if(a[i]%2==1){
			cnt++;
			tmp= (char)(i+'A');
		}
		if(cnt>1){
			cout << "I'm Sorry Hansoo" << "\\n";
			exit(0);
		}
		ret.append(a[i]/2, (char)(i+'A'));
	}
	rev = ret;
	reverse(rev.begin(), rev.end());
	ret.append(tmp);
	ret.append(rev);

	cout << ret << "\\n";
	return 0;
}

 

배열로 풀어도 성능의 큰 차이는 없었다.

 

---

다. 참고

 

예쁜 코드가 있어서 들고 왔다. (큰돌 선생님 코드다.)

//백준 1213번: 팬린드롬
#include <iostream>
#include <string>

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"; 
}

 

• 문자열의 문자들의 수를 배열에 저장하는 부분

// good
for(char a : s)cnt[a]++;
// bad
for(int i=0; i<name.length(); i++){
	a[name[i] - 'A']++;
}

 

• 주어진 수가 홀수인지 확인하는 방법

// good
if(cnt[i] & 1){
// bad
if(a[i]%2==1){

 

→ 실제로 돌려보니 성능은 크게 다르진 않았지만 이해하기 더 쉽다.

 

---