[백준] 회문인 수 (11068) - Javascript

문제 설명 : https://www.acmicpc.net/problem/11068

 

 

문제 요약 :

1. 주어진 수의 회문(팰린드롬) 여부 구하기
2. 단, 주어진 수를 2~64 진법으로 변환시킨 수도 해당한다.

 

문제 풀이 시간 : 1시간

문제 성공 여부 : 실패

 

 

접근 방법(실패) :

1. n진수로 변경하는 함수 구현
2. 팰린드롬 여부 확인 함수 구현

분명히 문제가 없다고 생각했는데, 계속 메모리 초과가 발생하였다

 

곧바로 js 입출력의 한계라 판단하여 구글링을 하여 process.stdout.write 등 수많은 글을 읽어보며 시도해 봤지만 결과는 동일하였다.

 

js에 대한 불신과 불만이 점점 커지는 와중 채점 기록에는 수많은 js 동료들의 흔적이 남아있었다.

내가 문제였다..

 

맘을 다잡고 다시 내 코드의 허점을 찾아본 순간 머리를 맞는 듯한 오류를 찾아버렸다.

 

N진수 변환 함수

function tenToBaseN(n, num) {
  let baseN = ""; // n진수
  
  while (num > 0) {
    const mod = num % n; // 나머지 값
    num = Math.floor(num / n); // n으로 나누기

    baseN += mod;
  }

  return baseN;
}

 

내가 구현했던 n진수 변환 함수인데..

 

분명 로직상 문제가 없다고 생각한 코드인데 큰 문제가 있었다.

 

바로, baseN을 문자열로 구현한 것이다.

 

n은 최대 64까지 올라갈 수 있기 때문에 하나의 비트가 10이 넘을 수 있다는 사실을 전혀 생각하지 못했었다.

 

따라서 11진수의 10은 자연스럽게 1과 0으로 분리되었고

문자끼리 팰린드롬을 비교한 결과 당연하게도 오류가 날 수 밖에 없었다.

 

 

 

 

접근 방법(성공) :

1. 진법 변환 함수를 배열로 구현하기

function tenToBaseN(n, num) { 
  const baseN = []; // 베열로 구현하여 비교!
  while (num > 0) {
    const mod = num % n;
    num = Math.floor(num / n);

    baseN.push(mod);
  }

  return baseN;
}

 

이렇게 배열의 인덱스에 숫자를 넣게 되면 비트 별로 정확한 비교연산이 가능해진다!

 

팰린드롬 비교 함수

function isPalindrome(num) {
  const mid = Math.floor(num.length / 2);
  const len = num.length - 1;

  for (let i = 0; i < mid; i++) {
    if (num[i] !== num[len - i]) return false;
  }

  return true;
}

 

팰린드롬 비교 함수도 매우 간단하다.

첫번째 숫자와 마지막 숫자를 mid까지 비교해 주면 된다~

 

전체 코드(성공) :

function sol() {
  const fs = require("fs");
  const filePath = process.platform === "linux" ? "dev/stdin" : "./input.txt";
  const [n, ...input] = fs.readFileSync(filePath).toString().trim().split("\n");

  let ans = "";
  for (const num of input) {
    let canPlindrome = false;

    for (let i = 2; i <= 64; i++) {
      const base_n = tenToBaseN(i, num);

      if (isPalindrome(base_n)) {
        canPlindrome = true;
        break;
      }
    }

    ans += canPlindrome ? "1\n" : "0\n";
  }

  return ans;
}

function tenToBaseN(n, num) {
  const baseN = [];
  while (num > 0) {
    const mod = num % n;
    num = Math.floor(num / n);

    baseN.push(mod);
  }

  return baseN;
}

function isPalindrome(num) {
  const mid = Math.floor(num.length / 2);
  const len = num.length - 1;

  for (let i = 0; i < mid; i++) {
    if (num[i] !== num[len - i]) return false;
  }

  return true;
}

const ans = sol();
console.log(ans);

 

난이도가 매우 쉬운 문제라 생각했는데 조금 더 꼼꼼하게 접근할 필요성을 느꼈다

또한, 언어에는 문제가 없고 나를 먼저 의심하자는 것을 다시 한번 배우게 되었다..