[백준15657_자바스크립트(javascript)] - N과 M(8)

🔴 문제

N과 M(8)

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const inputs = fs
  .readFileSync(path)
  .toString()
  .trim()
  .split('\n')
  .map((it) => it.split(' ').map(Number));

const [n, m] = inputs.shift();
const numbers = inputs.pop().sort((a, b) => a - b);

let ans = '';
const bt = (selected, cnt, start) => {
  if (cnt === m) {
    ans += selected.trim() + '\n';
    return;
  }

  for (let i = start; i < n; i++) {
    bt(selected + ' ' + numbers[i].toString(), cnt + 1, i);
  }
};

bt('', 0, 0);

console.log(ans);

🟢 풀이

⏰ 소요한 시간 : -

먼저 입력받은 숫자를 정렬해준다.
그 후 백트래킹 함수는 지금까지 선택된 수를 나타내는 selected와 몇 개까지 선택했는지 세어주는 cnt, 그리고 비내림차순을 체크해줄 start 변수를 받는다.
cnt가 m이라면 즉 다 선택했다면 문자열을 정답 문자열에 더해주고, 다 선택하지 않았다면 반복문을 돌며 다음 숫자를 선택해주면 된다.
이 때 반복은 start라는 변수부터 시작해서 비 내림차순 조건을 충족한다.

🔵 Ref