[node.js,백준]6603 - 로또

목차

 

 

 문제

링크

https://www.acmicpc.net/problem/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이 하나 주어진다. 

 

출력

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

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

 

주저리

다음순열 로직을 이용해서 주어진 배열을 선택하지 않은수는 0 선택한 수는 1의 배열로 만들어서 쭉 풀어준다.

ex) 8개 배열이면 [1,1,1,1,1,1,0,0]부터해서 다음순열 로직을 활용하는 것 하지만 앞에처럼 선언이되면 순서가 반대로되기때문에 한번 reverse()로 뒤집어줘서 로직을 수행후에 마지막에 결과 배열들을 다시 reverse해서 가져와준다.

 

풀이

 초기 조합 배열 생성

• 초기에 6개의 '1'을 배열의 끝에 배치하고, 나머지는 '0'으로 채웁니다. 이 배열은 조합의 기반으로 사용됩니다.

 nextPermutation 함수

이 함수는 주어진 배열을 사전 순으로 다음 순열로 재배치하는 역할을 합니다.

• 순열 찾기: 배열을 역순으로 검사하며 현재 요소가 이전 요소보다 클 때까지 진행합니다. 이 지점을 찾으면, 순열의 다음 변경 지점이 됩니다.
• 요소 교환과 순서 뒤집기

 조합 생성과 출력

nextPermutation 함수를 반복적으로 호출하여 모든 조합을 생성합니다.

• 조합 추출과 저장: 각 순열에서 1이 설정된 위치의 원소들을 선택하여 조합을 만듭니다. 이 조합들은 배열에 저장됩니다.
• 최종 출력: 모든 조합이 생성되면, 저장된 배열을 역순으로 출력하여 사전 순으로 조합들을 제시합니다.

 

 코드

// 로또
var fs = require('fs');
var input = fs.readFileSync('/dev/stdin').toString();

let real = input.trim().split("\n");
let rest = real;
// rest = rest.map((row) => {
//     row = row.split(" ").map(Number);
//     return row;
// })
// sec = sec.trim().split(" ").map(Number);

function swap(arr, index1, index2) {
    // 임시 변수를 사용하여 두 값을 교환
    var temp = arr[index1];
    arr[index1] = arr[index2];
    arr[index2] = temp;
}
async function nextPermutation(arr, n) {
    let i = n - 1;
    while (i > 0 && arr[i - 1] >= arr[i]) i -= 1;
    if (i <= 0) return false;
    let j = n - 1;
    while (arr[j] <= arr[i - 1]) j -= 1;
    // console.log({ i, j })
    // console.log('1', arr);
    swap(arr, i - 1, j);
    // console.log('2', arr);
    j = n - 1;
    while (i < j) {
        swap(arr, i, j);
        // console.log('3', arr);
        i += 1; j -= 1;
    }
    return true;
}

async function solution() {
    let returns = [];

    for (let row of rest) {
        if (row === '0') break;
        let [T, ...rests] = row.trim().split(" ").map(Number);
        let Array_01 = [];
        for (let i = 0; i < rests.length; i++) {
            if (i < 6) {
                Array_01.push(1);
            }
            else {
                Array_01.push(0);
            }
        }
        Array_01.reverse();
        // console.log({ Array_01 })
        let isNP = null;
        let innerReturns = [];
        let size = 0;
        do {
            let ans = [];
            Array_01.forEach((n, i) => {
                if (n === 1) {
                    ans.push(rests[i]);
                }
            })
            // console.log({ ans, Array_01 })
            innerReturns.push(ans.join(" "));
            size++;
            isNP = await nextPermutation(Array_01, T);

        }
        while (isNP)
        innerReturns.reverse();
        returns.push(...innerReturns, " ");
        // console.log({ innerReturns })
    }

    console.log(returns.join("\n"))


}
solution();