(C++) - 백준(BOJ) 1213번 : 팰린드롬 만들기 답

www.acmicpc.net/problem/1213

1213번: 팰린드롬 만들기

문자열 처리 문제였습니다.

 

풀이방법

 1. 입력받은 이름의 각 문자마다 알파벳의 개수를 세줍니다.

 2. 알파벳의 개수가 홀수인 알파벳이 2개 이상이라면 팰린드롬을 만들 수 없으므로 "I'm Sorry Hansoo"를 출력하고 프로그램을 종료합니다.

 3. 아닌 경우 :

   3-1. 'A'부터 'Z'까지 나온 알파벳의 개수/2만큼 알파벳을 정답변수 ans에 더해줍니다.

   3-2. 남은 홀수개의 알파벳 1개는 팰린드롬을 만들려면 중앙에 위치해야 하므로 그 후에 더해줍니다. (홀수개였던 알파벳이 없을 수도 있으니 %2가 양수인 알파벳에 한에서만 실시합니다)

   3-3. 'Z'부터 'A'까지 나온 알파벳의 개수/2만큼 알파벳을 정답변수 ans에 더해줍니다.

  4. 정답을 출력합니다.

Code

#include <bits/stdc++.h>
using namespace std;
string s, ans;

int alpha[26];

bool canNotMakePalin(){
    int cnt = 0;
    for(int i = 0; i < 26; i++)
        if(alpha[i] % 2 == 1) 
            cnt++;
    return cnt > 1;
}

int main(){
    cin >> s;
    for(int i = 0; i < s.size(); i++) alpha[s[i]-'A']++;
    
    if(canNotMakePalin()) {cout << "I'm Sorry Hansoo"; return 0;}

    for(int i = 0; i < 26; i++)
        for(int j = 0; j < alpha[i]/2; j++)
            ans += i + 'A';

    for(int i = 0; i < 26; i++)
        if(alpha[i]%2) 
            ans += i + 'A';

    for(int i = 25; i >= 0; i--)
        for(int j = 0; j < alpha[i]/2; j++)
            ans += i + 'A';

    cout << ans <<'\n';
}

 

Test Case

 몇 가지 반례를 직접 작성해 보았습니다. 

 

input

ABBBCCA

답
ABCBCBA

 

input

AABBNNBB

답

ABBNNBBA

 

input

AABBCV

답

I'm Sorry Hansoo