DAY5 중급 - 백준 1213번 (C++)

www.acmicpc.net/problem/1213

1213번: 팰린드롬 만들기

 

<답안>

#include <iostream>
using namespace std;
int main()
{
    //A : 65 -> 0
    int count[26] = {0};
    int num = 0;
    int index = 0;
    int oddCount = 0;
    int evenCount = 0;
    int temp = 0;
    string name;
    cin>>name;
    for(int i=0; i<name.size(); i++)
    {
        count[(int)name[i]-65]++;
    }
    //총개수, 홀수 카운트 증가
    for(int i=0; i<26; i++)
    {
        if(count[i] != 0)
        {
            num++;
            if(count[i]%2 == 1)
            {
                oddCount++;
                index = i;
            }
            else
                evenCount++;
        }
    }
    //한문자만 입력된 경우 그대로 출력
    if(num == 1)
    {
        for(int i=0; i<26; i++)
        {
            if(count[i] != 0)
            {
                temp = count[i];
                while(temp--)
                    cout<<(char)(i+65);
            }
        }
        return 0;
    }
    //두문자 이상 -> 판별
    else if(num == 0)
    {
        cout<<"I'm Sorry Hansoo";
    }
    else
    {
        //홀수 문자가 1개인 경우 : 나머지 반전
        if(oddCount == 1)
        {
            for(int i=0; i<26; i++)
            {
                if(count[i] != 0)
                {
                    temp = count[i]/2;
                    while(temp--)
                        cout<<(char)(i+65);
                }
            }
            cout<<(char)(index+65);
            for(int i=25; i>=0; i--)
            {
                if(count[i] != 0)
                {
                    temp = count[i]/2;
                    while(temp--)
                        cout<<(char)(i+65);
                }
            }
        }
        //홀수가 없는경우
        else if(oddCount == 0)
        {
            for(int i=0; i<26; i++)
            {
                if(count[i] != 0)
                {
                    temp = count[i]/2;
                    while(temp--)
                        cout<<(char)(i+65);
                }
            }
            for(int i=25; i>=0; i--)
            {
                if(count[i] != 0)
                {
                    temp = count[i]/2;
                    while(temp--)
                        cout<<(char)(i+65);
                }
            }
        } //정상 종료
        //비정상 종료
        else
        {
            cout<<"I'm Sorry Hansoo";
        }
    }
    return 0;
}

 

<설명>

이문제는 "반례"가 사람잡아먹던 문제였다

일단 머리속에 드는 경우는

1. 한문자만 입력받은 경우 -> 그대로 한문자 입력개수만큼 반복하여 출력(그대로 출력)

2. 모든문자 짝수번 입력 -> 각 문자 알파벳 순으로 개수/2번씩 출력 -> 알파벳 순서 반대로 개수/2번씩 출력

3. 홀수번 입력문자 1개 + 짝수번 입력문자 조합 -> 짝수번 반절씩 출력 -> 홀수문자 출력 -> 짝수번 반절씩 출력

 

이렇게 생각하고 풀었다가 계속된 오류가 발생하였다 어렵게 찾은 반례는 이렇다

AABBBCC -> ACBBBCA? or ABCBCBA?

 

그렇다 오른쪽답처럼 홀수개 문자여도 알파벳 순으로 출력한다음 가운데 추가해주는 식으로 출력해야 했던것이다

 

이점만 알고나면 나머지는 크게 어렵진 않았다

 

string으로 입력받아 크기만큼 for 돌리며 해당 알파벳(A : 0 ~ Z : 25)에 해당되는 인덱스의 count[i]를 증가시키며 각 문자의 개수를 센다

입력이 종료되고나선 다시 for 돌리며 count값이 0이아닌 위치에 도달됬을때 글자수 num을 증가시키며

count값이 홀수이면 oddCount증가, 짝수이면 evenCount를 증가시킨다

 

그러면 1번의 케이스라면 num = 1이기 때문에 count!=0인 i번째 글자를 개수만큼 출력시킨다

num=1이 아니라면 num=0인 문자가 없는 경우도 있지만

크게 문자카운트 값이 홀수가 1번 있는경우, 짝수만 있는경우, 그외의 에러의 경우로 나뉜다

 

2번의 케이스 : 짝수만 있는 경우는 for i=0 ~ 25까지 돌리며 count값이 있는경우 문자를 개수/2만큼 출력시키고

다시 for i=25 ~ 0까지 돌리며 동일하게 출력시키면 된다

 

3번의 케이스 : 홀수가 1번 포함된 경우는 생각해보면 홀수 또한 짝수+1 이므로 짝수와 동일하게 개수/2씩 출력시키고

가운데 문자만 한번 출력한다음 다시 개수/2씩 출력시키면 된다

 

그러면 정상적으로 케이스가 나뉘게 된다