[Algorithm] 로또 (백준 - 6603)

📋 문제

독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다.

로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다.

예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34])

집합 S와 k가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 주어진다.

입력의 마지막 줄에는 0이 하나 주어진다. 

출력

각 테스트 케이스마다 수를 고르는 모든 방법을 출력한다. 이때, 사전 순으로 출력한다.

각 테스트 케이스 사이에는 빈 줄을 하나 출력한다.

입출력 예

예제 입력

예제 출력

7 1 2 3 4 5 6 7 8 1 2 3 5 8 13 21 34 0

1 2 3 4 5 6 1 2 3 4 5 7 1 2 3 4 6 7 1 2 3 5 6 7 1 2 4 5 6 7 1 3 4 5 6 7 2 3 4 5 6 7 1 2 3 5 8 13 1 2 3 5 8 21 1 2 3 5 8 34 1 2 3 5 13 21 1 2 3 5 13 34 1 2 3 5 21 34 1 2 3 8 13 21 1 2 3 8 13 34 1 2 3 8 21 34 1 2 3 13 21 34 1 2 5 8 13 21 1 2 5 8 13 34 1 2 5 8 21 34 1 2 5 13 21 34 1 2 8 13 21 34 1 3 5 8 13 21 1 3 5 8 13 34 1 3 5 8 21 34 1 3 5 13 21 34 1 3 8 13 21 34 1 5 8 13 21 34 2 3 5 8 13 21 2 3 5 8 13 34 2 3 5 8 21 34 2 3 5 13 21 34 2 3 8 13 21 34 2 5 8 13 21 34 3 5 8 13 21 34

✏️ 풀이

이 문제는 재귀를 이용해서 풀었다. 

 

우선 케이스가 여러번 주어지기 때문에 console.log를 한 번만 찍기 위해서 answers라는 배열을 만들어서 담았다. 또한. 답으로 나올 숫자들이 오름차순으로 정렬되어야 하기 때문에 주어진 케이스를 정렬시켜주고 조합을 구했다. 

 

재귀로 search라는 함수를 계속해서 호출하면서 select에 숫자를 선택해서 push했다. 이때 숫자들에서 숫자를 선택하기 위한 반복문을 수행할 때 시작할 인덱스를 계속해서 넘겨주며 중복선택이 일어나지 않도록했다. 총 6개의 숫자를 뽑아야 하기 때문에 고른 숫자가 6개 이상이 되는 시점(select.length >= 6)에 answer에 넣어주었고 더 이상 재귀가 일어나지 않도록 return했다. 이후 return이 되고 선택했던 숫자를 pop하면서 반복문이 계속 수행되며 모든 조합을 선택하게 된다.

 

하나의 케이스를 다 선택하게 되면 answer에 모든 숫자들이 담겨있는디 "\n"으로 join 해주게 되면 줄바꿈되어 answers에 들어가게 되고 마지막에 케이스마다 공백을 넣어주며("\n"으로 다시 한번 join) 출력하며 문제를 해결했다.

⌨️ 코드

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './testcase/6603.txt';

const inputs = fs.readFileSync(filePath).toString().trim().split('\n');

const answers = [];
for (const input of inputs) {
  if (input === '0') break;

  const nums = input.split(' ').map(Number);
  nums.shift();
  nums.sort((a, b) => a - b);
  const answer = [];

  const len = nums.length;
  const select = [];
  const search = idx => {
    if (select.length >= 6) {
      answer.push(select.join(' '));
      return;
    }

    for (let i = idx; i < len; i++) {
      select.push(nums[i]);
      search(i + 1);
      select.pop();
    }
  };

  search(0);
  answers.push(answer.join('\n'));
}
console.log(answers.join('\n\n'));