[노드JS/알고리즘] 백준 - 1213번 팰린드롬 만들기

[문제]

1213번: 팰린드롬 만들기

 

[코드&풀이]

팰린드롬을 생성하기 위해서는 홀수 개를 가진 알파벳의 개수가 한 개이거나 / 모두 짝수 개를 가진 알파벳이어야 한다.

빈도수 계산을 위해 Map을 이용하였고, 

'정답이 여러 개일 경우에는 사전 순으로 앞서는 것을 출력한다.'는 조건이 있어 loocaleCompare로 사전식 정렬을 해주었다.

 

- 코드 요약

1. 홀수 개의 알파벳의 개수(oddCnt)와 해당하는 알파벳(oddChar)을 계산한다.

2. 홀수 개의 알파벳의 개수가 두개 이상이면 I'm Sorry Hansoo를 출력한다.

3. 2번에 해당하지 않는다면, 팰린드롬 생성이 가능하다.

  3-1.  빈도수에 2를 나눈 몫만큼 알파벳을 s에 추가한다.

  3-2. firstHalf에 만들어진 s를 추가하고, secondHalf에는 firstHalf를 뒤집어서 저장해준다.

4. oddCnt에 맞춰 답을 출력한다.

 

-예시

팰린드롬 생성 과정은 예시를 보면 더 간단하다!

첫 번째 예시) AABB가 있다면 -> table에서 절반을 가져와 firstHalf에 AB를 저장한다. -> AB를 뒤집은 BA를 추가해준다. -> 팰린드롬은 ABBA가 된다.

두 번째 예시) AABBB가 있다면 -> table에서 절반을 가져와 firstHalf에 AB를 저장한다. -> 홀수개의 알파벳 체크 시 저장해둔 oddChar를 추가 -> AB를 뒤집은 BA를 추가해준다. -> 팰린드롬은 ABABA가 된다. 

 

즉, 모두 짝수 개일 경우, firstHalf + secondHalf

홀수 개의 알파벳이 한개 있을 경우, fistHalf + oddChar+ secondHalf이다.

 

// !! 홀수 개를 가진 알파벳의 개수가 2개 이상이면 팰린드롬 생성 불가
// 홀수 개를 가진 알파벳의 개수가 한개이거나 모두 짝수 개를 가진 알파벳의 경우 팰린드롬으로 생성 가능하다.

const sen = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "input.txt")
  .toString()
  .trim()
  .split("");

const getPalindrome = (sen) => {
  // 알파벳별 빈도수 계산
  let table = new Map();
  for (const ch of sen) {
    if (table.has(ch)) table.set(ch, table.get(ch) + 1);
    else table.set(ch, 1);
  }
  // 사전식 정렬
  table = Object.values([...table]).sort((a, b) => a[0].localeCompare(b[0]));

  // 홀수개의 알파벳 개수와 해당하는 알파벳 체크
  let oddCnt = 0;
  let oddChar = "";
  for (const [key, val] of table) {
    if (val % 2) {
      oddCnt++;
      oddChar = key;
    }
  }

  // 홀수개의 알파벳이 두개 이상이면 팰린드롬 생성 불가!
  if (oddCnt > 1) return "I'm Sorry Hansoo";

  // 팰린드롬 생성 과정
  let firstHalf = "";

  for (let [key, val] of table) {
    let s = "";
    for (let i = 0; i < Math.floor(val / 2); i++) {
      s += key;
    }
    firstHalf += s;
  }
  const secondHalf = firstHalf.split("").reverse().join("");
  return oddCnt === 1
    ? firstHalf + oddChar + secondHalf
    : firstHalf + secondHalf;
};

console.log(getPalindrome(sen));