백준 15650번: N과 M (2) - javascript

백준 15650번: N과 M (2)

문제 설명

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

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

입력

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

출력

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

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

접근

이미 포스팅했던 백준 15649번 N과M의 응용 버전이다.
기본적인 풀이 방법은 저 포스팅을 보면된다.

그러면 이번에 바뀐 조건을 뭘까?
지난번과 다르게 이번 문제에서는 고른 수열은 오름차순 이여야만 한다고 조건을 추가했다.
지난번에는 중복만 금지되었지만 이제는 각 수열자체도 오름차순이여야만 하는 것이다.
방법은 간단하다.

지난번 코드에서는 중복을 체크하기위해 중복체크용 배열을 추가했었다.
그러면 이번에는 함수의 매개변수에 오름차순 체크용 변수를 추가하면 된다.
배열을 할 필요도없이 0값인 변수 k를 넣어서 현재 i와 비교해서 큰지 작은지를 비교하면된다.
기존에 있던 조건과 and로 붙여서 k보다 현재 i가 크면 지금 만드는 수열은 오름차순이라 판단하고, k값을 현재 i값으로 바꾼뒤 다음 함수 매개변수로 넘겨주면 꾸준하게 오름차순인 수열이 나오는 것이다.

정답 코드

const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});
let input = [];
let list = [];
let result = [];
let check = new Array(9).fill(false);
rl.on('line', function (line) {
  input.push(line);
})
  .on('close', async function () {
  // 답안 작성
  let answer =0;
  
  input = input[0].split(' ');
  let n = input[0];
  let m = input[1];
  re(0,n,m,0);  
  console.log(result.join('\n'));  
  process.exit();
});

let re = function(cnt,n,m,k){
  if(cnt==m){
    result.push(list.join(' '))
    return 1;
  }
  for(let i=1;i<=n;i++){
    if(!check[i] && k<i){
      check[i] = true;
      list[cnt] = i;
      k = i;
      re(cnt+1,n,m,k);
      check[i] = false;
    }
  }
  return 1;
}