알고리즘 :: 백준 :: 1213 - 팰린드롬 만들기

 

 

❔문제

🔗문제링크

 

🔄 문제 및 입출력 조건 파악

입력: 알파벳 대문자로만 된 최대 50글자 문자열

출력:

• 팰린드롬을 만들 수 있다면, 팰린드롬을 출력하고
• 팰린드롬을 만들 수 없다면, "I'm Sorry Hansoo"를 출력

✏️ 문제풀이

팰린드롬을 만들기 위해서는 반드시 문자열이 중간지점을 기점으로 대칭이어야 합니다.

대칭이 되기 위해서는, 홀수번 등장하는 알파벳이 없거나 1개만 존재해야 합니다.

즉, 홀수번 등장하는 문자가 2개 이상이라면, 해당 문자열은 팰린드롬을 만들 수 없습니다.

 

이런 맥락에서 보면, 팰린드롬은 다음과 같은 형태입니다.

• 2회 이상 등장한 문자들을 각각 등장횟수 절반만큼 먼저 사전순으로 나열합니다.
• 이렇게 나열한 문자열은 접두사(prefix)입니다. 나중에 이걸 뒤집어서 뒤에 붙이면, 모든 등장횟수를 사용한게 됩니다.
• 홀수번 등장한 문자가 1개 있다면, 여기 중간에 문자 1개를 넣어줍니다.
  • 예를 들어, 3번 등장한 문자가 있다면,
    • 접두사를 만드는 과정에서 1번 들어갔을 겁니다. (3 / 2 = 1)
    • 중간에 1번 넣어주고
    • 접두사를 뒤집어서 접미사로 넣어주니 나머지 1번 들어갑니다.
  • 9번 등장한 문자가 있다면,
    • 접두사를 만드는 과정에서 4번 들어갔을 겁니다. (9 / 2 = 4)
    • 중간에 1번 넣어주고,
    • 접두사를 뒤집어서 접미사로 넣어주니 나머지 4번 들어갑니다.

📝 코드

#include <bits/stdc++.h>
using namespace std;

array<int, 26> alpha;

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	string name;
	cin >> name;
	for (auto c : name) alpha[c - 'A']++;
	
	int cntOdd = 0, posOdd = -1;
	for (int i = 0; i < 26; ++i) {
		if (alpha[i] & 1) {
			cntOdd++;
			posOdd = i;
		}
	}
	// If there are more than two odd alphabets, we can't create a palindrome.
	if (cntOdd > 1) {
		cout << "I'm Sorry Hansoo";
		exit(0);
	}
	// Step 1. make left half of a result string.
	string result = "";
	result.reserve(name.length());
	
	for (int i = 0; i < 26; ++i) {
		while (alpha[i] > 1) {
			result.push_back('A' + i);
			alpha[i] -= 2;    // [Caution!] Not divide 2.
		}
	}
	// Step 2. make right half of the result by reversing the left side.
	string temp{result};
	reverse(begin(temp), end(temp));
	
	// Step 3. If the odd alphabet is, add that to the center of result.
	if (posOdd != -1 && alpha[posOdd]) result.push_back('A' + posOdd);
	
	// Step 4. Concatenate left side + (odd char) + right side to make result
	result += temp;
	cout << result;
}

 

🔗 코드 링크

🕧 결과