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

🔴 문제

N과 M(10)

🟡 Sol

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

const [n, m] = inputs[0];
const numbers = inputs[1].sort((a, b) => a - b);
const visited = Array.from({ length: numbers.length }).map(() => false);

let ans = '';

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

  let preNumber = -1;

  for (let i = start; i < n; i++) {
    if (visited[i] === false && preNumber !== numbers[i]) {
      visited[i] = true;
      bt([...selected, numbers[i]], i);
      visited[i] = false;
      preNumber = numbers[i];
    }
  }
};

bt([], 0);
console.log(ans);

🟢 풀이

⏰ 소요한 시간 : -

다른 n과 m 시리즈와 똑같이 풀이 하면된다. 사전 순으로 출력할 것이기 때문에 숫자를 선택할 때 부터 정렬된 numbers 배열에서 순회를 하고, 한 번 고른 숫자는 다시 사용하지 못하기 때문에 visited 배열을 만들어줬다.
백트래킹 내부는 m개의 숫자를 모두 뽑았을 때 종료 처리 해주고 모두 뽑지 않았다면 반복문을 돌면서 숫자를 추가해 재귀함수를 호출해주면된다.
이 때 이전에 고른 인덱스 보다 큰 인덱스에서부터만 값을 선택할 수 있기 때문에 start 위치부터 반복을 수행하며 한 번 고른 수는 못고르기 때문에 visited 배열이 false라면 true로 바꿔준다.
그리고 중복 체크도 해주어야 하는데 이는 이전에 뽑은 숫자가 지금 내가 뽑을 숫자와 같은지 다른지 체크해주면 된다. 따라서 preNumber이라는 변수를 만들어 이전에 뽑은 숫자를 기억해주면 된다.

🔵 Ref