[백준 15657] N과 M (8) with Node.js

문제 링크

https://www.acmicpc.net/problem/15657

15657번: N과 M (8)

풀이

const solve = (N, M, arr) => {
  const permutation = [];
  const output = [];
  const recursion = () => {
    if (permutation.length === M) {
      output.push(permutation.join(' '));
    } else {
      for (const i of arr) {
        if (permutation[permutation.length-1] > i) continue;
        permutation.push(i);
        recursion();
        permutation.pop(i);
      }
    }
  };
  recursion();
  console.log(output.join('\n'));
};

const [ N, M, ...arr ] = require('fs').readFileSync('/dev/stdin').toString().trim().split(/\s+/).map(v => +v);
arr.sort((a, b) => a - b);
solve(N, M, arr);

먼저 주어진 수들을 오름차순으로 정렬한다.

 

permutation의 마지막 수보다 작거나 같은 수를 선택한다.

하나의 수를 선택하면 재귀적으로 다시 순회하면서 permutation의 길이가 M이 될 때까지 계속 수를 선택하여 permutation에 push한다.

선택된 수들이 M개가 되면 더 이상 수를 선택하지 않고 output에 지금까지 선택된 수들을 문자열로 저장한다.

재귀호출에서 빠져나오면서 재귀호출 직전에 선택되었던 수를 pop한다.

recursion()이 끝나면 지금까지 output에 저장한 수열을 출력한다.

 

이렇게 하면 M 개의 수로 이루어진 중복을 포함하는 비내림차순 수열을 오름차순으로 출력할 수 있다.