팰린드롬 만들기

문제

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

언어

JavaScript

순서도

이름에서 각 알파벳의 개수 세기
알파벳의 개수가 홀수인 경우의 개수 세기
알파벳의 개수가 홀수인 경우가 2 번 이상이면 “I’m Sorry Hansoo” 출력
알파벳의 개수가 홀수인 경우가 1 번 이하라면 사전 순으로 가장 앞선 팰린드롬 만들어서 출력

문제 풀이 step 1

임문빈을 도와서 임한수의 영어 이름을 팰린드롬으로 바꾸는 프로그램을 작성하는 문제입니다.
팰린드롬이란?
- 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열 등을 말합니다.
팰린드롬을 만들 수 있는 경우는?
- 문자열을 구성하는 모든 문자의 개수가 짝수개인 경우
- 문자열을 구성하는 문자 중 단 하나의 문자만 홀수개인 경우

문제 풀이 step 2

위의 팰린드롬에 관한 정보를 바탕으로 임한수의 영어 이름으로 팰린드롬을 만들 수 있는지 판별하고, 만약 만들 수 있다면 사전 순으로 가장 앞서는 팰린드롬을 만들어서 출력하면 됩니다.
우선, 이름에서 각 문자의 개수를 세기 위해서 26 크기의 배열을 선언하고, 각 문자의 개수를 세어줍니다.
각 문자의 개수 중에서 홀수인 경우를 셉니다.
- 홀수인 경우가 2 번 이상일 경우 “I’m Sorry Hansoo” 를 출력합니다.
- 홀수인 경우가 1 번 이하일 경우 팰린드롬으로 만들어서 출력합니다.
팰린드롬을 만들기 위해서 우선 팰린드롬을 반으로 쪼갤 때의 왼쪽 문자열을 먼저 만듭니다.
- 빈 문자열을 생성합니다.
- 알파벳 순서대로 이름의 각 문자의 개수의 반만큼씩 빈 문자열에 추가해서 팰린드롬의 반을 구현합니다.
- 위 과정을 통해서 만든 팰린드롬의 반을 뒤집어서 반대쪽 팰린드롬의 반을 구현합니다.
- “팰린드롬의 반”과 “홀수인 문자 한 개”와 “반대쪽 팰린드롬의 반”을 모두 합치면 팰린드롬이 됩니다.
위 과정을 통해서 만든 팰린드롬을 출력하면 정답입니다.
추가 설명은 주석으로 작성하겠습니다.

후기

팰린드롬에 대한 이해 부족과 사전순으로 앞선 문자열에 대한 이해 부족으로 상당한 시행 착오를 겪었습니다.
“AABBCCCDD” 일 경우, 사전순으로 앞선 팰린드롬은 “ABCDCDCBA” 인데, “ABDCCCDBA” 라고 생각을 했었습니다.
홀수인 문자들이 모두 뭉쳐서 가운데로 가야한다고 잘못 생각해서 상당히 많은 시간을 허비했습니다.

소스 코드

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

const solution = (input) => {
	const name = input[0].split("").sort();

	// 이름에서 각 문자의 개수 세기
	const alphabets = Array(26).fill(0);
	for (let i = 0; i < name.length; i++) {
		alphabets[name[i].charCodeAt(0) - "A".charCodeAt(0)] += 1;
	}

	let oddCnt = 0;
	let midIdx = -1;
	for (let i = 0; i < 26; i++) {
		if (alphabets[i] === 0 || alphabets[i] % 2 === 0) continue;

		// 문자의 개수가 홀수인 경우 세기
		oddCnt += 1;
		midIdx = i;
	}

	// 문자의 개수가 홀수인 경우가 2 이상인 경우
	if (oddCnt > 1) return "I'm Sorry Hansoo";

	let res = [];
	for (let i = 0; i < 26; i++) {
		if (alphabets[i] === 0) continue;

		// 각 문자의 개수의 반 만큼씩 배열에 추가
		const alphabet = String.fromCharCode("A".charCodeAt(0) + i);
		for (let j = 0; j < parseInt(alphabets[i] / 2); j++) {
			res.push(alphabet);
		}
	}

	let palindrome = "";

	// 팰린드롬을 반으로 쪼갤 때의 왼쪽 문자열
	for (let i = 0; i < res.length; i++) {
		palindrome += res[i];
	}
	// 문자의 개수가 홀수인 문자 추가
	if (oddCnt === 1)
		palindrome += String.fromCharCode("A".charCodeAt(0) + midIdx);
	// 팰린드롬을 반으로 쪼갤 때의 오른쪽 문자열
	for (let i = res.length - 1; i >= 0; i--) {
		palindrome += res[i];
	}

	return palindrome;
};

console.log(solution(input));