[BOJ] 1213 팰린드롬 만들기

문제 이해하기

• 영어 문자열을 받아서 팰린드롬으로 바꿔야 한다

예제 입력으로 문제 이해하기

• 입력 : AABB
• 출력 : ABBA
  1. A : 2개
     B : 2개
  2. BB
  3. ABBA
• 입력 : AAABB
• 출력 : ABABA
  1. A : 3개
     B : 2개
  2. BB
  3. ABABA

알고리즘

1. 알파벳의 개수를 찾는다
2. 알파벳의 개수가 홀수인 알파벳이 2개 이상인 경우는 불가능 한 경우이다.
3. 사전순으로 앞서는 것을 출력해야 하므로 Z > A 순으로 데이터를 앞뒤로 붙여준다.
4. 알파벳의 개수가 홀수가 1개 있었던 경우 문자열의 중간에 넣어준다. 

코드

#include <bits/stdc++.h>
using namespace std;
string s, ret;
char mid;
int cnt[200], flag;
int main(){
	cin >> s;
    // step 1 : 알파벳의 개수를 저장
    for(int n : s) ++cnt[n];
    
    for(int i = 'Z' ; i >= 'A' ; i--){
      	if(cnt[i]){
         	// 홀수 여부 판별
            if(cnt[i] & 1){
            	mid = char(i); 
                --cnt[i];
            	++flag;
            }
            // step 2 : 홀수 알파벳이 두개 이상이라면 종료 
            if(flag >=2) break;
            // step 3 : 문자열 앞뒤로 문자 붙이기  
            for(int j = 0 ; j < cnt[i] ; j += 2) {
            	ret = ret + char(i);
                ret = char(i) + ret;
            }
        }
    }
    
    if(flag == 1){ ret.insert(ret.begin() + ret.size() / 2, mid);}
    if(flag == 2){ cout << "I'm Sorry Hansoo"; }
    else { cout << ret; }
}

정리

• 알파벳의 개수를 저장하는 로직 
• 홀수 여부 판별 로직 
• 문자열 중간에 값 넣는 로직 

느낀점

• 쉬운 문제는 아니다. 문자열 앞뒤로 문자를 붙이거나, 홀수인 경우에는 cnt개수를 줄여주는 부분이 이해가 쉽진 않다.