백준 6603번: 로또 - javascript

3 분 소요

백준 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

출력
2 3 4 5 6
2 3 4 5 7
2 3 4 6 7
2 3 5 6 7
2 4 5 6 7
3 4 5 6 7
3 4 5 6 7

2 3 5 8 13
2 3 5 8 21
2 3 5 8 34
2 3 5 13 21
2 3 5 13 34
2 3 5 21 34
2 3 8 13 21
2 3 8 13 34
2 3 8 21 34
2 3 13 21 34
2 5 8 13 21
2 5 8 13 34
2 5 8 21 34
2 5 13 21 34
2 8 13 21 34
3 5 8 13 21
3 5 8 13 34
3 5 8 21 34
3 5 13 21 34
3 8 13 21 34
5 8 13 21 34
3 5 8 13 21
3 5 8 13 34
3 5 8 21 34
3 5 13 21 34
3 8 13 21 34
5 8 13 21 34
5 8 13 21 34

접근

N과M(2)를 여러번 돌리는 문제다.
N과M(2)를 기반으로 풀이했으니 먼저 N과M(2)포스팅을 보고 오시는 걸 추천드린다.

기본적으로 N과M(2)의 코드를 가져오되, N과M은 1부터 i까지의 범위였고, 이번문제는 각 줄에 테스트 케이스의 길이와 테스트 케이스가 주어진다고 했다.
그러니 재귀 함수에서 깊이 매개변수는 6으로 고정, 오름차순인지 판별하는 k를 i랑 비교하는게 아닌 min과 주어진 테스트 케이스 배열 numbers의 i값과 비교하게 변경하면된다.
한 테스트 케이스에 대해서 재귀가 전부 끝나면 전역 선언한 result배열에 담기게 되는데, 이 result배열을 전체 테스트케이스들을 돌리는 반복문동안 answer라는 변수를 만들어 결과를 담아두고 초기화 시켜서 다음 테스트 케이스에 대한 재귀함수 작업을 또 돌리면된다.

그냥 N과M(2)을 여러번 시행하면서 입,출력 받을 반복문 하나만 만들면 되는거라서 간단했다.

정답 코드

const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});
let input = [];
let result = [];
let list = [];
let check = new Array(13).fill(false);
rl.on('line', function (line) {
  input.push(line);
})
  .on('close', async function () {
  // 답안 작성
  let answer = [];  
  input.pop(); 
  answer = lotto(input)  
  console.log(answer)
  process.exit();
});
//재귀 함수를 반복하면서 결과를 매번 저장할 반복문 함수
let lotto = function(input){
  let answer = '';
  for(let i=0;i<input.length;i++){
    let tmp = input[i].split(' ');
    let m = tmp.splice(0,1)
    let n = tmp.length;
    re(0,n,6,tmp,-1);
    answer += result.join('\n') + '\n\n'    
    result = [];
    check = new Array(13).fill(false);
    list = []
  }  
  return answer.slice(0,-2);
}
//기존 오름차순 수열만 구하는 재귀함수
let re = function(cnt,n,m, numbers,min){
  if(cnt==m){
    result.push(list.join(' '))
    return ;
  }
  for(let i=0;i<n;i++){
    if(!check[i]&&numbers[i]*1>min){
      check[i] = true;
      list[cnt] = numbers[i];
      re(cnt+1,n,m,numbers,numbers[i]*1);
      check[i] = false;
    }
  }
  return ;
}

Twitter Facebook LinkedIn

ryeon

백준 6603번: 로또 - javascript