[Algorithm] Baekjoon 1213번 : 팰린드롬 만들기

https://www.acmicpc.net/problem/1213

1213번: 팰린드롬 만들기

 
int counts[26] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    string s;
    cin >> s;
 
    bool isOdd = s.size() % 2 == 1 ? true : false;
 
    for (int i = 0; i < s.size(); ++i)
    {
        ++counts[s[i] - 65];
    }
 
    char oddChar = ' ';
    int answerIndex = 0;
    string answer;
    answer.resize(s.size());
 
    for (int i = 0; i < 26; ++i)
    {
        int charCount = counts[i];
        if (charCount == 0) continue;
 
        for (int j = 0; j < charCount / 2; ++j)
        {
            answer[answerIndex] = answer[s.size() - 1 - answerIndex] = i + 65;
            ++answerIndex;
        }
 
        if (charCount % 2 == 1)
        {
            if (oddChar == ' ')
            {
                oddChar = i + 65;
            }
            else
            {
                cout << "I'm Sorry Hansoo";
                return 0;
            }
        }
    }
    
    if (oddChar != ' ')
    {
        answer[s.size() / 2] = oddChar;
    }
 
    cout << answer;
}

 

주어진 문자열이 팰린드롬인지 확인하는 간단한? 문제이다.

 

먼저 문자열의 각 문자들의 개수를 카운팅한다.

그다음 i는 0부터 26까지, 즉 A부터 Z까지 순회한다. 정답을 출력할 때 사전순으로 출력해야 하기 때문이다.

2로 나눈 몫의개수만큼 정답문자열(answer)을 채워준다.

정답문자열은 당연히 주어지는 문자열의 크기와 같으며, 미리 resize해줘야 한다. 시작부분,끝부분을 동시에 채워줘야하기 때문이다.

 

예를들어 AABB일 경우, A의 카운팅개수는 2개이다.

그리고 정답문자열은 미리 resize했기 때문에   '/ / / /' 상태일 것이다. (/은 비어있다는 뜻)

이상태에서 A의 카운팅개수는 2개, 즉 정답문자열에 처음과 끝부분에 채우는 행위를 1번만 수행한다.(카운팅개수를 2로 나눈몫의 개수만큼 채워준다는게 이 의미였다.)

 

그러면 'A / / A'가 된다. 위 코드의 32번째 줄에 해당한다.

매 동작마다 정답문자열의 어느위치에 채워줘야할지 정해줘야하기 때문에 answerIndex를 따로 선언해서 가지고 있어준다.

 

그리고 채워주는것과 별개로, 개수가 홀수인 문자가 2개이상일 경우에는 팰린드롬이 안되기 때문에, 해당부분을 코드에 반영하면 된다.