[C++] [CSES] Palindrome Reorder (Introductory Problems)

CSES의 열 두번째 문제입니다.

문자열을 받아서 아무 팰린드롬을 만들거나, 만들 수 없다고 하거나 판정을 해야 합니다.

 

Task

Given a string, your task is to reorder its letters in such a way that it becomes a palindrome (i.e., it reads the same forwards and backwards).

Input

The only input line has a string of length n consisting of characters A–Z.

Output

Print a palindrome consisting of the characters of the original string. You may print any valid solution. If there are no solutions, print "NO SOLUTION".

Constraints

• 1≤n≤1e6

Example

Input:
AAAACACBA

Output:
AACABACAA

 

Code

#include<bits/stdc++.h>
using namespace std;
string s;
int ar[26];
int oddAlpha, oddCnt;
int main(){
    cin >> s;
    for (char c : s){
        ar[c - 'A']++;
    }
    for (int i=0;i<26;i++){
        if (ar[i] % 2 == 1){
            oddCnt++;
            oddAlpha = i;
        }
    }
    if (oddCnt >= 2){
        cout << "NO SOLUTION";
        return 0;
    }
    for (int i=0;i<26;i++){
        for (int j=0;j<ar[i]/2;j++){
            cout << (char)(i + 'A');
        }
    }
    if (oddCnt) cout << (char)(oddAlpha + 'A');
    for (int i=25;i>=0;i--){
        for (int j=0;j<ar[i]/2;j++){
            cout << (char)(i + 'A');
        }
    }
}

생각해야 하는 것

• 각 문자가 몇 번씩 등장하는지를 저장하는 배열을 만들어야 합니다.
• 문자가 홀수 번 등장하는 경우가 없거나 한가지인 경우만 팰린드롬을 만들 수 있음을 알 수 있습니다.
• 아무 팰린드롬을 만들면 되지만 저는 문자상으로(lexicographically) 가장 작은 팰린드롬을 만들었습니다. 가장 쉽게 팰린드롬을 만들 수 있기 때문입니다.