[백준] 1213 팰린드롬 만들기 (Javascript)

문제

BOJ1213_팰린드롬 만들기

코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('');
input.sort(); // 알파벳 오름차순 정렬

let left = 0;
let right = input.length;
let mid = (left + right) >> 1;

const palindrome = Array(right);
const alphabet = new Map();
for (const c of input) {
    if (alphabet.has(c)) alphabet.set(c, alphabet.get(c) + 1);
    else alphabet.set(c, 1);
}

let oddCount = 0;
for (let [key, value] of alphabet) {
    if (value % 2 === 1) {
        oddCount++;
        palindrome[mid] = key;
        value--;
    }
    // 개수가 홀수인 알파벳이 2개 이상일 경우
    if (oddCount > 1) {
        console.log("I'm Sorry Hansoo");
        process.exit();
    }
    for (let i = 0; i < value / 2; i++) {
        palindrome[left++] = key;
        palindrome[right--] = key;
    }
}

console.log(palindrome.join(''));

팰린드롬이란?

거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열 등

접근법

• 개수가 홀수인 알파벳의 경우 한 개는 팰린드롬의 가장 가운데에 들어가야 하고, 나머지는 양쪽으로 몰아놔야 한다.
• 개수가 짝수인 알파벳의 경우 양쪽으로 몰아놔야 한다.
• 개수가 홀수인 알파벳이 2개 이상이면 팰린드롬이 될 수 없다.
• 사전순으로 앞서는 것을 출력하려면 사전순으로 빠른 알파벳이 팰린드롬의 앞쪽에 있으면 된다. 따라서 팰린드롬을 만들때 'A'부터 배치해주도록 한다.
• 알파벳을 양쪽으로 몰아넣기 위해서는 왼쪽 인덱스, 오른쪽 인덱스가 필요하다.
• 알파벳과 그 알파벳의 개수를 키-값 쌍으로 저장해놓는다.

객체 리터럴 대신 Map을 사용한 이유

Map은 삽입 순서를 보장하기 때문에 input에서 알파벳 순으로 정렬된 순서가 Map안에서도 그대로 유지된다. 따라서 사전순으로 빠른 알파벳부터 팰린드롬 배열에 삽입할 수 있기 때문에 Map을 사용했다. 또한 반복문 사용이 쉽다는 점도 있다.