[백준]6603번 '로또' 문제풀이 - JavaScript

[백준]6603번 '로또' 문제풀이 - JavaScript

1. 문제

독일 로또는 {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가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성하시오.

1.1. 입력

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

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

1.2. 출력

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

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

1.3. 예제 입력 1

      

      

      

    
    

      <bash />
    
7 1 2 3 4 5 6 7
8 1 2 3 5 8 13 21 34
0

1.4. 예제 출력 1

      

      

      

    
    

      <bash />
    
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

2. 👉 풀이 코드

      

      

      

    
    

      <javascript />
    
const fs = require('fs');
const file = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const input = fs.readFileSync(file).toString().trim().split('\n');

let answer = '';

for (let tc = 0; tc < input.length - 1; tc++) {
  const testCase = input[tc].split(' ');
  const k = Number(testCase[0]);
  const arr = testCase.slice(1).map(Number);
  const visited = new Array(k).fill(false);
  const result = [];
  let temp = '';

  function dfs(start) {
    if (result.length === 6) {
      temp += result.join(' ') + '\n';
      return;
    }
    for (let i = start; i < k; i++) {
      if (visited[i]) continue;
      visited[i] = true;
      result.push(arr[i]);
      dfs(i + 1);
      result.pop();
      visited[i] = false;
    }
  }
  dfs(0);

  answer += temp + '\n';
}

console.log(answer);

3. 👉 풀이 해설

이 문제는 K개 중에서 6개를 골라 모든 조합을 구하는 문제로 볼 수 있다.

반응형

테스트케이스를 받는 반복문 안에 입출력을 받아주고 방문 처리를 하는 배열과 재귀를 호출하면서 숫자를 담을 배열을 선언 해주고, 테스트 케이스의 결과를 담을 문자열 변수를 선언해 줬다.

 

dfs함수에서는 중단점으로 최종적으로 숫자를 담는 result 배열의 길이가 6이라면  temp에 넣어주도록 했다.

재귀를 호출하면서 result 배열의 길이가 6이 아니라면 반복문을 실행하는데,

start부터 k까지 순회하도록 해주고 방문을 확인한 뒤, 방문하지 않은 인덱스라면 방문처리를 해준 뒤 arr의 해당인덱스의 값을 result에 넣어줬다.

재귀 함수가 끝나면 다시 꺼내주고 방문처리를 해제하는 식으로 해서 k개의 원소에서 6개의 모든 조합을 구할 수 있다.

 

마지막으로 테스트 케이스마다 담은 값들을 넣은 temp 변수를 answer에 넣어주고 모든 테스트케이스가 종료되면 answer를 출력해서 정답처리를 받았다.