백준 15665번: N과 M (11) - javascript

백준 15665번: N과 M (11)

문제 설명

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

• N개의 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.

입력

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

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

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

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

접근

백준 15664번 N과M(10)을 풀었다면 바로 조건만 바꿔서 제출하면 되는 문제다. 기본적인 풀이 방법은 저 포스트에 담겨있다.

(10)번과 다른점은 먼저 비내림차순이 아니다.
그리고 중복도 허용한다.
다만, 동일한 수열의 중복은 허용되지않는다.

이 3가지 조건만 고려해서 10번 문제의 풀이에서 재귀부분의 마지막 매개변수를 현재 i 값으로 넘겨주던 것을 초기값 0인 start로 계속 넘겨주면 비내림차순의 조건이 해제된다.
두번째로 중복체크 해주던 check[i] 배열과의 bool값 체크조건도 해제해 준다.
세번째인 수열의 중복체크는 이미 prev 변수로 체크하고있으니 따로 안해도 된다.

ps
잊고 있었는데 N과 M 문제 초기에는 N의 범위가 작아서 전역 boolean 배열 check의 길이를 9로 잡았었는데 다행하게도 여태까지는 N이 7이하로 주어져서 문제가 없었다…
이 부분을 나중에는 전역변수로 선언만 하고 input을 입력 받은 뒤 N기준으로 배열값을 조정해야 한다.
이번문제도 상관없는 부분이지만 생각나서 써봤다.

정답 코드

const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});
let input = [];
let list = [];
let result = [];
let numbers = [];
// ------------------------ 추신의 check 배열은 바로 이 부분, 나는 무작정 9로 고정해놓고 쓰고있었다 ---------------//
let check = new Array(9).fill(false);
rl.on('line', function (line) {
  input.push(line);
})
  .on('close', async function () {
  // 답안 작성
  let answer =0;  
  let input_num = input[0].split(' ');
  numbers = input[1].split(' ').sort((a,b) => a-b);
  let n = input_num[0];
  let m = input_num[1];
  re(0,n,m,0);  
  console.log(result.join('\n'));  
  process.exit();
});

let re = function(cnt,n,m,start){
  if(cnt==m){    
    result.push(list.join(' '))
    return ;
  }
  let prev = -1;
  for(let i=start;i<n;i++){    
    if(prev!=numbers[i]){            
      prev = numbers[i];
      list[cnt] = numbers[i];
      re(cnt+1,n,m,start);     
    }
  }
}