[코딩테스트]백준 - 로또

로또

문제

독일 로또는 {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이 하나 주어진다.

출력

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

예제 입력 1

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

예제 출력 1

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

출처

• Contest > University of Ulm Local Contest > University of Ulm Local Contest 1996 F번
• 문제의 오타를 찾은 사람: apjw6112 jh05013
• 문제를 번역한 사람: baekjoon

링크

• PKU Judge Online
• ZJU Online Judge
• TJU Online Judge
• HDU Online Judge

해결한 코드

function b6603(){
  var fs = require('fs');
  var input = fs.readFileSync('/dev/stdin').toString().split('\n');
//var input = fs.readFileSync(__dirname + '/stdin.txt').toString().replace(/\r/g, "").split('\n');
  var testCase = []
  for (var i = 0; i < input.length - 1; i++) {
    // 0 은 아예 무시하려고 input.length-1 까지만 해줌 
     var e = input[i].split(' ')
     e = e.map((e) => parseInt(e))
     testCase.push(e)
  }
  for (var j = 0; j < testCase.length; j++) {
     testCase[j] = testCase[j].slice(1, testCase[j].length)
  }
  var array = []
  for (var t = 0; t < testCase.length; t++) {
      var ans = [] 
      // 다음 테스트 케이스를 위해 ans초기화
      for (var a = 0; a < testCase[t].length; a++) {
         backTrack(ans, testCase[t][a], testCase[t], testCase[t][a].toString())
      }
    array.push(ans)
    // 현재 테스트 케이스의 재귀를 돌고 반환된 현재 ans를 array에 넣음 
  }
  for(var l = 0; l<array.length; l++){
    for(var m=0; m<array[l].length; m++){
      console.log(array[l][m])
    }
    console.log()
  }
}

function backTrack(ans, a, testCase, str){
  str = str.split(' ').sort((a,b) => a-b) // str을 오름차순으로 정렬 
  if(str.length === 6){
    str = str.join(' ') // 공백 포함한 문자열로 다시 붙이기 
    if(ans.every(e => e !== str)){ 
      // 중복된 str은 ans에 삽입하지 않도록 
      ans.push(str)
    }
    return;
  }
  var findNextIndex = testCase.findIndex(e => e === a)
  str = str.join(' ')
  for(var i = findNextIndex+1; i<testCase.length; i++){
  	backTrack(ans, testCase[i], testCase, str + ' ' + testCase[i].toString())
  }
}

b6603()

알고리즘

• 숫자판 점프 알고리즘과 비슷하게 풀었다.

1. (0,0)번째 부터 끝까지 완전탐색하여 6개의 숫자 묶음을 만든다.

👉🏻 이를 위해 재귀를 돌린다.
ex. 예를 들면

testCase = [
  [7, 1, 2, 3, 4, 5, 6, 7],
  ...(생략)
]

1-1. 0번째 인덱스 숫자를 지운다(어차피 숫자 갯수 알려주는거라 없어도 무방).

for (var j = 0; j < testCase.length; j++) {
     testCase[j] = testCase[j].slice(1, testCase[j].length)
  }

그러면 testCase는 다음과 같이 수정된다.

testCase = [
  [1, 2, 3, 4, 5, 6, 7],
  ...(생략)
]

1-2. testCase(0,0) 부터 차례대로 완전 탐색을 한다.

backTrack(ans, testCase[t][a], testCase[t], testCase[t][a].toString())

testCase(0,0) = 1이니까 '1' 형태로 backTrack에 들어간다.

function backTrack(ans, a, testCase, str){
  // ans = [], a = 1, testCase = [1,2,3,4,5,6,7], str = '1'
  str = str.split(' ').sort((a,b) => a-b) 
  // str = ['1']
  if(str.length === 6){
    // 현재 str의 길이가 6이 아니기 때문에 이쪽으로 들어오지 x 
    str = str.join(' ') 
    if(ans.every(e => e !== str)){ 
      ans.push(str)
    }
    return;
  }
  var findNextIndex = testCase.findIndex(e => e === a)
  // findNextIndex = 0
  str = str.join(' ')
  // str = '1'
  for(var i = findNextIndex+1; i<testCase.length; i++){
    // i = 1
    backTrack(ans, testCase[i], testCase, str + ' ' + testCase[i].toString())
    // ans = [], a = testCase[1] => 2, testCase = [1,2,3,4,5,6,7], str = '1 2' 
  }

이런 식으로 진행된다.
그러다가 a = 5일 때, a = 6의 재귀를 불러 str = '1 2 3 4 5 6' 인 때가 오게 되면,

function backTrack(ans, a, testCase, str){
  // ans = [], a = 6, testCase = [1,2,3,4,5,6,7], str = '1 2 3 4 5 6'
  str = str.split(' ').sort((a,b) => a-b) 
  // str = ['1', '2', '3', '4', '5', '6']
  if(str.length === 6){
    // 현재 str의 길이가 6 => 여기 들어옴 
    str = str.join(' ') 
    // str = '1 2 3 4 5 6'
    if(ans.every(e => e !== str)){ 
      // ans에 겹치는 거 없음 
      ans.push(str)
      // ans = ['1 2 3 4 5 6']
    }
    return;
  }
  var findNextIndex = testCase.findIndex(e => e === a)
  // findNextIndex = 5
  str = str.join(' ')
  // str = '1 2 3 4 5 6'
  for(var i = findNextIndex+1; i<testCase.length; i++){
    // i = 6
    backTrack(ans, testCase[i], testCase, str + ' ' + testCase[i].toString())
    // return ans = ['1 2 3 4 5 6'], a = 5 로 돌아옴 
    // 그럼 이제 a = 7로 재귀 go !
  }

이런 식으로 재귀를 돌며 차곡차곡 완전 탐색을 한다.

1-3. testCase(t, 0) 째가 되면

새로운 테스트 케이스 시작이니까 ans를 초기화 한다. ans = []
그럼 이전 로또 번호들은 어떡해?? => 초기화 하기 전에 빈배열에 미리 push 해둔다. array.push(ans)

2. 각 테스트 케이스 간에 줄바꿈을 해주며 출력한다.

array에 각 테스트별 배열이 담겨져 있으니, 배열 간 빈줄을 추가해주고 출력하면 된다.

숫자판 점프 문제를 풀고 난 후 접근한 게 도움이 많이 된 것 같다.
역시 코테 문제에 재귀는 빠질 수 없는 것... 재귀 잘 익히자 ! 아자아자 ! 💪🏻