[백준/C & C++] 1213 팰린드롬 만들기

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

1213번: 팰린드롬 만들기

 

c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct alphabet
{
	char s;
	int n;
};

int cmp(const void* a, const void* b)
{
	return strcmp((char*)a, (char*)b);
}

int main()
{
	char name[51], result[51], index=0, odd=0;
	scanf("%s", name);
	int len = strlen(name);
	qsort(name, len, sizeof(char), cmp);
	struct alphabet* arr = (struct alphabet*)malloc(sizeof(struct alphabet) * len);

	arr[0].s = name[0];
	arr[0].n = 1;
	for (int i = 1; i < len; i++)
	{
		if (name[i] != arr[index].s)
		{
			if (arr[index].n % 2 == 1) odd++;
			index++;
			arr[index].s = name[i];
			arr[index].n = 1;
		}
		else arr[index].n++;

	}

	if ((arr[index].n) % 2 == 1) odd++;
	if (odd > 1)
	{
		printf("I'm Sorry Hansoo");
		return 0;
	}

	for (int i = 0, j=0; i <= index; i++)
	{
		if (arr[i].n % 2 == 1)
		{
			result[len / 2] = arr[i].s;
			arr[i].n--;
		}
		for (; arr[i].n > 0; arr[i].n -= 2, j++)
		{
			result[j] = arr[i].s;
			result[len - j - 1] = arr[i].s;
		}
	}

	for (int i = 0; i < len; i++) printf("%c", result[i]);
	free(arr);
	return 0;
}

c++

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

struct alphabet
{
	char s;
	int n;
};

int main()
{
	char name[51], result[51];
	int index = 0, odd = 0;
	cin >> name;
	int len = strlen(name);
	sort(name, name + len);
	alphabet* arr = new alphabet[len];

	arr[0].s = name[0];
	arr[0].n = 1;
	for (int i = 1; i < len; i++)
	{
		if (name[i] != arr[index].s)
		{
			if (arr[index].n % 2 == 1) odd++;
			index++;
			arr[index].s = name[i];
			arr[index].n = 1;
		}
		else arr[index].n++;
	}

	if (arr[index].n % 2 == 1) odd++;
	if (odd > 1)
	{
		cout << "I'm Sorry Hansoo";
		return 0;
	}

	for (int i = 0, j = 0; i <= index; i++)
	{
		if (arr[i].n % 2 == 1)
		{
			result[len / 2] = arr[i].s;
			arr[i].n--;
		}
		for (; arr[i].n > 0; arr[i].n -= 2, j++)
		{
			result[j] = arr[i].s;
			result[len - j - 1] = arr[i].s;
		}
	}

	for (int i = 0; i < len; i++) cout << result[i];
	delete[]arr;
	return 0;
}

코드 설명

각각의 알파벳이 몇 번 나오는지 저장하기 위해서 구조체를 만들었다. 입력받는 이름을 저장할 문자열 배열 name과 결과를 저장할 문자열 배열 result를 선언한다. 이름을 입력받고는 이름의 길이를 len에 저장하고, 이름을 정렬한다. 

c++은 algorithm 헤더에서 sort를 제공하기 때문에 이를 사용했고, c의 경우에는 qsort를 사용했다. 그리고 내가 만든 구조체를 배열의 원소로 사용할 것이므로 구조체 배열을 동적할당으로 생성한다. 

 

이름의 첫 번째 문자를 arr[0].s에 저장하고, 1을 arr[0].n에 저장한다. 이후 반복문을 이름의 두 번째 문자부터 끝까지 돌도록 한다. 현재의 이름 문자와 arr[index].s와 비교한다. 이때 index는 가장 마지막으로 저장된 구조체 원소의 인덱스이다. 현재의 이름 문자와  arr[index].s가 다르다면 이제 새로운 문자가 등장한 것이다. arr[index].s가 몇 번 등장했는지 봐야하는데, 이때는 홀수인지만 본다. 홀수라면 홀수의 개수를 저장하는 odd를 1씩 증가시킨다. 새로운 문자를 저장하기 위해서 index를 1 증가시키고, 문자와 등장횟수를 저장한다. 만약 현재의 이름 문자와  arr[index].s가 같다면 단순하게 등장횟수를 증가시켜준다.

 

odd를 구한 이유는 팰린드롬을 만들기 위해서는 홀수가 최대 1번만 등장해야 한다. aab의 경우에는 aba로 팰린드롬을 만들 수 있지만, aabc로는 팰린드롬을 만들 수 없기 때문이다. 위의 반복문에서 마지막 문자와 arr[index].s가 같은 경우에는  arr[index].n의 횟수만 증가시키고, 이 횟수가 홀수인지 확인하지 못했다. 따라서 if문으로 arr[index].n이 홀수인지 확인하고, 홀수라면 odd를 증가시킨다.

 

odd가 1보다 크다면, 이라면 홀수 번 등장한 알파벳이 두 개 이상 있다는 뜻이므로 바로 I'm Sorry Hansoo를 출력하고 프로그램을 종료시킨다. 그렇지 않다면 팰린드롬을 만들 수 있다!

 

반복문을 사용해서 결과를 만든다. arr에는 알파벳이 사전순으로 저장되어 있기 때문에 문자를 넣기만 하면 된다. arr[i].n % 2 == 1인 경우에는 arr[i].s가 홀수 번 등장한 경우이다. 홀수 번 등장한 경우에는 가운데에 해당 알파벳이 한 번 들어가야 한다. 따라서 result[len/2]에 arr[i].s를 넣고, 해당 알파벳의 등장횟수를 한 번 감소시킨다. arr[i].n이 0이 아니라면, arr[i].n은 짝수이다. 배열에서 값이 저장되지 않은 가장 왼쪽, 가장 오른쪽에 arr[i].s를 넣는다. 해당 알파벳을 다 사용할 때까지 양 끝에 알파벳을 넣는 과정을 반복한다. 

 

ex ) aabbc

a _ _ _  a - > ab_ba -> abcba

ex) aabbbcc

a _ _ _ _ _ a - > a b _ b _ b a ->  abcbcba

 

결과를 출력하고 동적배열을 해제하고 프로그램을 종료한다. 

 

느낀 점

아이디어는 금방 생각했다. 다만 한 번 틀렸는데, 코드 설명에서 빨간 색으로 표시한 부분을 하지 않았다. 여러 케이스들이 다 통과되길래 문제를 찾지 못하다가 겨우 찾았다.  자꾸 사소한 부분들을 놓친다. 열심히 연습해야겠다.