백준 1213 c++ "팰린드롬 만들기" -PlusUltraCode-

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

[필자 사고]

팰린드롬 문제이다.

N의 숫자가 50개가 주어져 있어서 부르스트로 생각은 했지만 경우의 수가 50!가 나와서 포기했다.

잠시 생각해보니 홀수 짝수 의 규칙성을 떠오릴 수 있다.

홀수개의 알파벳이 한개이거나 홀수개가 없으면 팰린드롬을 만들 수 있는거다.

그러나 만약 홀수개의 알파벳이 2개이상이면 만들지 못한다.

그래서 필자는 초기값 중간값 마지막 값 으로 3등분을 나눠서 문제를 해결했따.

초기값과 마지막값은 대칭개념이라 하나만 구하고 reverse 를 해주면 되고

중간값은 홀수 알파벳을 넣으면 해결된다.

 

아래는 자세한 코드 해설이다.

[코드 해설]

변수 설명

• str: 사용자로부터 입력받는 문자열입니다.
• hol: 알파벳 개수가 홀수인 문자가 있을 경우 그 문자를 저장하는 문자열입니다.
• resultMessage: 회문의 앞 절반을 구성하는 문자열입니다.
• arr: 알파벳 A부터 Z까지 각각 몇 번 등장했는지를 저장하는 크기 26의 정수형 벡터입니다.

---

주요 로직

1. 문자열 입력 및 초기화
   cin >> str;를 통해 문자열을 입력받고, arr 벡터를 0으로 초기화합니다.
2. 문자 빈도 계산
   문자열을 한 글자씩 순회하면서 각 문자의 등장 횟수를 arr에 저장합니다.
3. 회문 구성 가능성 체크 및 앞 절반 만들기
   알파벳 A부터 Z까지 26글자를 순회하면서
   • 등장 횟수가 홀수이면 hol에 해당 문자를 추가
   • 등장 횟수의 절반만큼 resultMessage에 문자를 추가
4. 회문 불가능한 경우 처리
   • hol에 저장된 문자가 2개 이상이면 회문 불가능 → "I'm Sorry Hansoo" 출력 후 종료
5. 회문 출력
   • resultMessage + hol + 뒤집은 resultMessage의 형태로 출력
   • reverse()를 이용해 resultMessage를 뒤집어서 뒤 절반을 구성함

[소스 코드]

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

string str, hol, resultMessage;
vector<char> arr;


void Game_Start() {
	cin >> str;
	hol = "";
	resultMessage = "";
	arr.assign(26, 0);

	for (int i = 0; i < str.size(); i++) {
		arr[str[i] - 'A']++;
	}

	for (int i = 0; i < 26; i++) {
		if (arr[i] % 2 == 1) {
			hol += i + 'A';
		}

		for (int j = 0; j < arr[i] / 2; j++) {
			resultMessage += i+'A';
		}
	}
	if (hol.size() > 1) {
		cout << "I'm Sorry Hansoo";
		return;
	}

	cout << resultMessage << hol;
	reverse(resultMessage.begin(), resultMessage.end());
	cout << resultMessage;

}

int main(void) {
	Game_Start();
}