문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

1부터 N까지 자연수 중에서 M개를 고른 수열
같은 수를 여러 번 골라도 된다.

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

시간 초과 코드

const fs = require("fs");
let input =
  process.platform === "linux"
    ? fs.readFileSync("/dev/stdin").toString().trim().split("\n")
    : fs
        .readFileSync(__dirname + "/input.txt")
        .toString()
        .trim()
        .split("\n");
const [N, M] = input[0].split(" ").map(Number);

const recursive = (arr) => {
  if (arr.length === M) {
    console.log(arr.join(" "));
    return;
  }

  for (let i = 1; i < N + 1; i++) {
    recursive([...arr, i]);
  }
};
recursive([]);

javascript로 알고리즘을 풀 때는 console.log가 시간 초과에 많은 영향을 준다고 한다. 그래서 str 변수에 출력할 글자를 저장해놓고 마지막에 출력했다.

통과 코드

const fs = require("fs");
let input =
  process.platform === "linux"
    ? fs.readFileSync("/dev/stdin").toString().trim().split("\n")
    : fs
        .readFileSync(__dirname + "/input.txt")
        .toString()
        .trim()
        .split("\n");
const [N, M] = input[0].split(" ").map(Number);
let str = "";

const recursive = (arr) => {
  if (arr.length === M) {
    str += arr.join(" ");
    str += "\n";
    return;
  }

  for (let i = 1; i < N + 1; i++) {
    recursive([...arr, i]);
  }
};
recursive([]);

console.log(str);

참고한 블로그 : https://dpsc615.tistory.com/148