[백준 / C언어] 1213번: 팰린드롬 만들기

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

1213번: 팰린드롬 만들기

 

난이도: solved.ac 실버 3

 

 

접근 방법

---

이름의 길이가 짝수면, 모든 알파벳의 개수가 짝수여야 한다.

이름의 길이가 홀수면, 홀수 개인 알파벳 1개 + 나머지 알파벳은 모두 짝수개여야 한다.

(홀수 = 홀수 + 짝수 + 짝수 이므로)

 

이름의 길이가 짝수일 때는 각 알파벳을 절반 개수씩 알파벳 순서로 출력하고 나머지는 반대 순서로 출력하면 된다.

이름의 길이가 홀수일 때는 일단 각 알파벳을 절반 개수씩 알파벳 순서로 출력을 하는데, 홀수 개인 알파벳은 2로 나눈 몫만큼 출력하고 맨 가운데에 하나를 따로 출력시켜 준다. 그리고 나머지 절반은 짝수일 때처럼 반대 순서로 출력하면 된다.

(Ex. ABBCABC -> ABC -> ABCB -> ABCBCBA)

 

풀이

---

먼저 문자열을 scanf로 받아준 후 각 자리의 알파벳이 몇 개씩 있는지 파악해 그 개수를 alpha라는 배열에 저장해주었다.

홀수 개인 알파벳의 개수가 몇 개인지 check라는 변수에 담아주었다.

문자열의 길이가 짝수 개인데 check가 1 이상이면 팰린드롬으로 못 만들기 때문에 I'm Sorry Hansoo를 출력한다.

문자열의 길이가 홀수 개일 때는, 홀수 개인 알파벳이 딱 한 개, 즉 check = 1 이여야 한다.

따라서 check = 1이 아니면 I'm Sorry Hansoo를 출력한다.

나머지 과정은 위의 '접근 방법'에서 설명한 대로 한다.

 

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
 
int main() {
	char arr[51];
	int* alpha = (int*)calloc(26, sizeof(int));
	scanf("%s", &arr);
	int len = strlen(arr);
 
	int i, j, check = 0, n;	// check: 홀수 개인 알파벳이 있을 때, n: 각 알파벳의 개수
	for (i = 0; i < len; i++)
		alpha[arr[i] - 'A']++;
 
	if (len % 2 == 0) {	// 길이가 짝수일 때
		for (i = 0; i < 26; i++) {
			if (alpha[i] % 2 != 0) {
				check = 1;
				break;
			}
		}
		if (!check) {
			for (i = 0; i < 26; i++) {
				n = alpha[i];
				for (j = 0; j < n / 2; j++)
					printf("%c", i + 'A');
				alpha[i] /= 2;
			}
			// 나머지 절반 출력
			for (i = 25; i >= 0; i--) {
				n = alpha[i];
				for (j = 0; j < n; j++)
					printf("%c", i + 'A');
			}
		}
		else
			printf("I'm Sorry Hansoo");
	}
	else {	// 길이가 홀수일 때
		int loc;	// 홀수 개인 알파벳 하나의 위치
		for (i = 0; i < 26; i++) {
			if (alpha[i] % 2 != 0) {
				loc = i;
				check++;
				continue;
			}
		}
		// 홀수 개인 알파벳이 하나만 나와서 출력 가능할 때
		if (check == 1) {
			for (i = 0; i < 26; i++) {
				n = alpha[i];
				for (j = 0; j < n / 2; j++)
					printf("%c", i + 'A');
				alpha[i] /= 2;
				if (i == loc)	// 홀수 개인 알파벳일 때
					alpha[i]++;
			}
			// 홀수 개인 알파벳을 가운데에 하나 출력함
			printf("%c", loc + 'A');
			alpha[loc]--;
			// 나머지 출력
			for (i = 25; i >= 0; i--) {
				n = alpha[i];
				for (j = 0; j < n; j++)
					printf("%c", i + 'A');
			}
		}
		// 홀수 개인 알파벳이 여러 개일 때
		else
			printf("I'm Sorry Hansoo");
	}
	free(alpha);
	return 0;
}