1213번: 팰린드롬 만들기 [C++]

1213번: 팰린드롬 만들기 (acmicpc.net)

1213번: 팰린드롬 만들기

 

팰린드롬 만들기

시간 제한            메모리 제한                  제출                           정답                   맞힌 사람            정답 비율

 

2 초

128 MB

15046

6124

4934

40.251%

문제

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

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

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

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

 

입력

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

출력

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

 

예제 입력 1 복사

AABB

예제 출력 1 복사

ABBA

예제 입력 2 복사

AAABB

예제 출력 2 복사

ABABA

예제 입력 3 복사

ABACABA

예제 출력 3 복사

AABCBAA

예제 입력 4 복사

ABCD

예제 출력 4 복사

I'm Sorry Hansoo

 

흐름

 

선생님 코드

#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); cout.tie(NULL);
	//1. 입력받기
	cin >> s;
	//2. 문자 카운트 하기 
	for(char a:s) cnt[a]++;
	//3. 팰린드롬 만들기 
	for(int i='Z';i>='A';i--){ //문자 오름차순으로 만들기 
		if(cnt[i]){
			//홀수개이면 
			if(cnt[i]&1){
				mid = char(i);
				flag++;
				cnt[i]--;
			}
			//홀수개 문자가 2개 이상이면 팰린드롬 아님 
			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);
	//4. 출력 
	//홀수개 문자 2개이면 팰린드롬 못만듬 
	if(flag==2) cout << "I'm Sorry Hansoo\n";
	else cout << ret << "\n";
}

 

유의할점

• 문자를 카운트할때는 count 배열을 생각하자. => count 배열은 숫자 존재 여부 꼭 파악하기 if (cnt[i]) 
• 팰린드롬은 홀수개 문자가 가운데 하나있어야한다.
• 문자의 개수가 홀수개임을 판별할때 cnt[i]%2==1 도 좋지만 cnt[i]&1==1 도 가능하다.(홀수는 이진수로 항상 1로 끝나기때문이다. 3=11, 5=101)
• 문자 오름차순으로 만들때는 Z부터 시작하여 붙인다.