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

🔴 문제

N과 M(5)

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const [nm, inputs] = fs.readFileSync(path).toString().trim().split('\n');
const [n, m] = nm.split(' ').map((it) => Number(it));
const numbers = inputs.split(' ').map((it) => Number(it));
numbers.sort((a, b) => a - b);

let answers = '';

const bt = (current, idx) => {
  if (idx === m) {
    const answer = current.join(' ');
    answers += answer + '\n';
    return;
  }

  for (let i = 0; i < n; i++) {
    const target = numbers[i];
    if (current.includes(target)) continue;
    bt([...current, target], idx + 1);
  }
};

for (const num of numbers) {
  bt([num], 1);
}

console.log(answers);

🟢 풀이

백트래킹유형 문제
입력받은 자연수 배열을 정렬한 뒤 bt알고리즘을 적용해주면 된다.
m개의 숫자를 선택해줘야 하므로 m개의 숫자를 다 선택했을 경우 재귀를 종료해주며 된다.
m개의 숫자를 아직 다 못고른 경우에는 하나의 숫자를 고르고 다시 재귀호출을 해주면되는데 문제에서 숫자를 중복해서 선택할 수 없다고 했으므로 숫자 선택시에 내가 선택한 숫자 배열에 들어있는지 확인하고 선택해준다.

🔵 Ref