CSES 1. Palindrome Reorder (1755)

출처: https://cses.fi/problemset/task/1755

---

문제 설명

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).

입력 

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

출력

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".

입력 예

AAAACACBA

출력 예

AACABACAA

제약조건

1 <= n <= 10^6

---

문제 풀이

입력을 읽고, A~Z 까지 나온 빈도수를 센다. 나타난 빈도수가 홀수인 경우가 2 이상이면 palindrome 을 만들수 없으므로 "NO SOLUTION"을 출력한다.

A~Z까지 나타난 문자의 빈도수/2인 문자열을 만들어서 앞쪽과 뒤쪽으로 붙여나간다.

 

홀수인 경우는 가운데에 빈도수가 홀수인 문자를 추가하고, 아니면 그냥 앞쪽과 뒤쪽을 붙여서 만든다.

프로그램 내용

#define MAX_S 1000000

int main()
{
    string in_str;
    cin >> in_str; /// input

	int ch_count[26] = {0};
    string out_str = in_str;

    int str_size = in_str.size();

    for(int i=0; i< in_str.size(); i++)
        ch_count[in_str[i]- 'A']++;

    int odd_count =0;
    int progress=0;
    char odd_char = '0';

    for(int i=0; i< 26; i++)
        if (ch_count[i] % 2)
            odd_count++;

		if (odd_count > 1)        
            cout << "NO SOLUTION" << endl;

		if (odd_count == 1 && odd_char == '0')
        	odd_char = 'A'+i;

    string first_half="";
    string second_half="";

    for(int i=0; i< 26; i++)
        char temp = 'A'+i;
        if (ch_count[i] > 0)
            string s(ch_count[i]/2, temp);
            first_half = first_half+s;
            second_half = s+second_half;

	if (odd_count == 1 && str_size %2 )
        out_str = first_half + odd_char + second_half;
    else
        out_str = first_half + second_half;

 

 

Introductory problems ( link )