BOJ - 6603 로또

1. 문제 링크 : https://www.acmicpc.net/problem/6603

2. 문제 티어: 실버2

3. 문제 유형 : 백트래킹 , 재귀

4. 문제 풀이 : 

 백트래킹 종류로, 단계적으로 문제를 푼다.

1) S, K를 입력 받는다. 문제에서 따로 이야기 없이 한 줄에서 입력 받게 했으므로 input에서 첫 번째 요소는 K 나머지는 배열로 입력 받는다.

2) 배열과 선택된 숫자(=K)개의 조합을 짜주는 재귀함수를 선언한다. 재귀함수인 이유는 조합은 중복이 허락되지 않기 때문에 기존에 만든 부분은 고정시켜야 하고 나머지 부분만으로 조합을 만들어야 중복이 허용되지 않는다.

예를 들어, [1, 2, 3, 4]에서 2개의 원소를 선택하는 경우:

• 가능한 조합: [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]

조합을 만들 때, 중복이 없도록 하기 위해 이전에 선택된 원소는 이후 선택 대상에서 제외해야 한다.

 

예제 시뮬레이션

입력: arr = [1, 2, 3, 4], selectNumber = 2

1. 첫 번째 반복 (fixed = 1)
   • rest = [2, 3, 4]
   • 재귀 호출: getCombinations([2, 3, 4], 1)
     • 결과: [[2], [3], [4]]
   • attached = [[1, 2], [1, 3], [1, 4]]
   • results = [[1, 2], [1, 3], [1, 4]]
2. 두 번째 반복 (fixed = 2)
   • rest = [3, 4]
   • 재귀 호출: getCombinations([3, 4], 1)
     • 결과: [[3], [4]]
   • attached = [[2, 3], [2, 4]]
   • results = [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4]]
3. 세 번째 반복 (fixed = 3)
   • rest = [4]
   • 재귀 호출: getCombinations([4], 1)
     • 결과: [[4]]
   • attached = [[3, 4]]
   • results = [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

최종 결과: [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

 

따라서 fixed, rest, attached를 분리해서 fixed를 rest에 추가한 attached를 결괏값 배열에 추가해주는 방식이어야 한다.

* 이렇게 조합을 만드는 방식을 통으로 외워서 자주 사용해야함을 느꼈다.

 

5. 코드

// 1. 값 입력 받기
const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");
let cases = [];

for(let i =0; i< input.length; i++) {
    let data = input[i].split(" ").map(Number);
    let k = data[0];
    if(k === 0) break;
    let numbers = data.slice(1);
    cases.push(numbers);
}

// 2. 조합 찾는 함수 선언
function getCombination(arr, selectNumber) {
    let results = [];
    // 만약 1개를 선택 시 전체 출력
    if(selectNumber === 1) return arr.map((value) => [value]);
    // 조합 생성
    arr.forEach((fixed, index, origin) => {
        // 현재 요소를 제외한 나머지 배열
        let rest = origin.slice(index + 1);
        // 재귀적으로 조합 생성
        let combinations = getCombinations(rest,selectNumber - 1);
        let attached = combinations.map((c) => [fixed, ...c]);
        results.push(...attached);
        });
        return results;
}

// 3. 입력 받은 배열을 위 함수를 통해 6개의 조합을 구하는 코드 
cases.forEach(numbers => {
    let combinations = getCombination(numbers, 6);
    combinations.forEach(combination => {
        console.log(combination.join(" "));
    });
    console.log(" "); // 각 테스트 케이스 사이에 빈 줄 출력
});