[백준6603_자바스크립트(javascript)] - 로또

🔴 문제

로또

🟡 Sol

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

function bt(lottos, selected) {
  if (selected.length === 6) {
    console.log(...selected);
    return selected;
  }

  for (const lotto of lottos) {
    if (!selected.includes(lotto)) {
      if (selected.length === 0) {
        bt(lottos, [...selected, lotto]);
      } else if (selected[selected.length - 1] < lotto) {
        bt(lottos, [...selected, lotto]);
      }
    }
  }
}

for (const input of inputs) {
  if (input[0] === 0) break;
  else {
    const [_, ...lottos] = input;
    bt(lottos, []);
    console.log();
  }
}

🟢 풀이

먼저 이미 선택한 수는 다시 선택할 수 없다는 점, 6개를 선택하면 선택을 중단하고 다음 경우의 수를 탐색해야 한다는 점에서 백트래킹 유형임을 알았다.
테스트 케이스가 여러개 이므로 입력받은 배열중 로또를 선택할 수 있는 번호를 담은 lottos를 따로 추출해준다. 0이면 종료하는 로직도 작성(맨 하단)
백트래킹 함수는 선택할 숫자들이 담긴 lottos배열과 내가 이미 선택한 selected 배열을 인자로 받는다.
내가 선택한 숫자의 개수가 6개라면 즉, selected 배열의 크긔가 6이라면 모두 선택했으므로 선택한 숫자를 출력해준다.
만약 6개를 다 선택하지 못했다면 숫자를 선택해서 재귀호출을 진행해주면 되는데 이때 내가 선택한 배열에 포함된 수인지, 오름차순을 만족하고 있는지 확인한 후 재귀호출해주면 된다.

🔵 Ref