[boj] 2661. 좋은수열 (node.js)

문제 요약

[boj] 2661. 좋은수열 (node.js)

풀이

• 1, 2, 3의 세 수만을 사용해서 길이가 N인 '좋은 수열'을 구하는 문제다.
• 좋은 수열은 수열 내부에서 임의의 길이를 가진 수열을 연속해서 선택했을 때, 그 어떤 수열도 동일하지 않은 경우를 말한다.
• 조건에 따라 자릿수에 해당하는 수열을 탐색하는 문제이므로, 조건을 만족하는 경우에 대해 재귀함수를 계속 호출해주면 된다.

내 풀이

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let _line = 0;
const input = () => stdin[_line++];

let stdin = [];
rl.on("line", function (line) {
  stdin.push(line);
}).on("close", function () {
  const N = input();
  rec(0, "");

  function rec(k, str) {
    if (k == N) {
      console.log(str);
      process.exit();
    } else {
      for (let i = 1; i <= 3; i++) {
        if (isGood(str + i)) rec(k + 1, str + i);
      }
    }
  }

  function isGood(str) {
    let len = Math.floor(str.length / 2);
    for (let i = 1; i <= len; i++) {
      if (
        str.slice(str.length - i * 2, str.length - i) ==
        str.slice(str.length - i)
      )
        return false;
    }
    return true;
  }
});

주절주절

• 강의를 들으며 완벽히 이해했다고 생각했던 완전탐색 문제였으나 이번 알고리즘은 꽤나 오랫동안 풀었다. 결국 이전에 풀이했던 N-Queen 알고리즘에서 힌트를 얻어 코드를 수정해 맞을 수 있었다.
• exit() 를 알고리즘 내부에서 처음 사용했다. 여러 번 재귀함수를 호출하여 결과값을 만들어내는데, return 으로 종료한다면 해당 함수를 호출한 시점으로 돌아가게 되므로, 연쇄적으로 종료될 수 있도록 구현해야 했다.
• 따라서, 최초로 반환한 답을 제외하고는 더 이상 탐색의 필요성이 없으므로 남은 호출을 모두 종료시키는 방법을 찾아봤고, process.exit()를 활용해 구현할 수 있음을 배워 이 방법으로 구현했다.