BaekJoon 1213 팰린드롬 만들기

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

소스결과 1988KB / 0 ms

출처 Backjoon

언어 C++ 17

분류 브루트포스(Brute Force), 정렬(Sorting)

연관 검색어 1213 C++, BOJ 1213 C++

 

설명

주어진 단어를 팰린드롬으로 바꿀 수 있는지에 대한 문제

팰린드롬이란 ? 위키백과 - 회문(Palindrome)

 

백준 문제 종류가 브루트포스이지만 풀고나서 채점결과를 보니 막상 그렇게 구현한사람은 찾기 힘들다.

정렬로 보면 Counting Sort에 속하기는 하지만 실질적으로 정렬을 하지는 않으니 정렬도 애매하다고 생각된다.

 

길이가 홀수인 경우, 짝수인 경우로 분류해서 해결하고

불가능한 경우가 명확하기 때문에 불가능한 경우를 제한다면 정답은 쉽게 나온다.

 

사전순으로 한개만 출력해야 한다는 점을 생각해야한다.

 

알고리즘

1. 문장을 입력 받은후 각각 알파벳의 갯수를 헤아려 저장한다.

2. 문장의 길이가 홀수인지 짝수인지 구분한다.

 2-1. 홀수인 경우 알파벳의 갯수가 홀수인 경우가 2개 이상 존재하면 만들 수 없다.

 2-2. 짝수인 경우 발파벳의 갯수가 홀수인 경우가 존재하면 만들 수가 없다.

3. 2의 경우에 속하지 않는 경우 회문을 만든다.

 3-1. 길이가 홀수인 경우 알파벳의 개수가 홀수인 알파벳을 가운데에 넣는다.

 3-2. 홀수 짝수 구분 없이 사전순으로 된 알파벳을 처음과 i 와 n - i -1 위치에 채워 넣는다.

4. 만들어진 회문/ 에러 메세지를 출력한다.

 

소스코드

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

using namespace std;

int alpha[26];

string func(int length)
{
	char res[51];
	memset(res, 0, sizeof(res));

	if (length % 2)
	{
		int min;
		for (min = 0; alpha[min] % 2 == 0; min++);

		res[length / 2] = char(min + 'A'); // 가운데 글자 채우기
		alpha[min]--;
	}

	int min = 0;
	for (int i = 0; i < length / 2; i++)
	{
		for (; alpha[min] == 0; min++); // 사전 최소 값 검색

		res[i] = res[length - i - 1] = min + 'A';
		alpha[min] -= 2;
	}
		
	return string(res);
}

int main()
{
	string input;
	int strLen;

	cin >> input;
	strLen = input.length();

	for (int i = 0; i < strLen; i++)
		alpha[input[i] - 'A']++;

	if (strLen % 2) // 길이가 홀수인 경우
	{
		int count = 0;

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

		if (count > 1) // 갯수가 홀수인 알파벳이 1개 이상이면 생성 불가
			cout << "I'm Sorry Hansoo";
		else
			cout << func(strLen);
	}
	else // 길이가 짝수인 경우
	{
		int count = 0;

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

		if (count > 0) // 갯수가 홀수인 알파벳이 존재하면 생성 불가
			cout << "I'm Sorry Hansoo";
		else
			cout << func(strLen);
	}

	return 0;
}