[백준] 1213번 - 팰린드롬 만들기

반응형

//#include <stdio.h>
#include <iostream>
#include <string>

#define _CRT_SECURE_NO_WARNINGS
using namespace std;


// 펠린드롬  65 = A
int main()
{

	int size;
	string arr;
	int odd_num = 0;
	int a_pre[27] = { 0 };
	char pelind[51] = { 0, };
	cin >> arr;
	size = arr.size();
	int fr = 0;
	int r = size - 1;
	for (int i = 0; i < size; i++)
	{
		a_pre[(arr[i] - '0') - 17]++;
	}
	for (int i = 0; i < 26; i++)
	{
		if (a_pre[i] != 0 && a_pre[i] % 2 == 1)
		{
			odd_num++;
		}
	}
	
	if (size % 2 == 0 && odd_num > 0)
	{
		cout << "I'm Sorry Hansoo" << endl;
		return 0;
	}
	else if (size % 2 == 1 && odd_num > 1)
	{
		cout << "I'm Sorry Hansoo" << endl;
		return 0;
	}
	for (int i = 0; i < 26; i++)
	{
		for (int j = a_pre[i]; j > 0; j--)
		{

			if (j % 2 == 0)
			{
				pelind[fr++] = (i + '0') + 17;
				pelind[r--] = (i + '0') + 17;
				j--;
			}
			else
			{
				pelind[size / 2] = (i + '0') + 17;
			}
		}
	}
	/*for (int i = 0; i < size; i++)
	{
		if (pelind[i] != 0)
			cout << pelind[i] ;
	}*/
	string res = string(pelind);
	cout << res;
	return 0;
}

시간이 오래 걸려서 풀었던 문제입니다.

 풀이 방식은 입력받은 알파벳을 횟수를 배열에 저장을 하고 펠린드롬을 만들 수 있는 조합인지를 먼저 판단합니다.

판단 방법

 1) 총 글자 수가 짝수인데 하나의 문자가 홀수 개이면 펠린드롬을 만들 수 없습니다.

 

 2) 총 글자 수가 홀수인데 둘 이상의 문자가 홀수 개이면 펠린드 옮을 만들 수 없습니다.

 

이 조건을 통과했다면 for 문을 통해서

혼자 있는 문자는 배열에 가운데 배치합니다.

문자가 짝수개가 있다면 

for문 한 번을 돌 때 각 문자가 앞, 뒤 모두 하나씩 배치해 주고 앞과 뒤를 재 정의해 줍니다.

 

알고리즘은 첫날 바로 세웠지만 for문에서 배열에 크기를 생각하지 못했던 실수를 해서 시간이 걸렸던 문제입니다.