백준 6603 로또 (파이썬, 자바)

풀이 1 (재귀 함수)

import sys


# N과 M을 풀었다면 똑같이 풀면 됨

def solve(depth, K):
    if depth == 6:
        print(*ans)
        return
    for i in S:
        if visited[i]:
            continue
        if not ans:
            ans.append(i)
            visited[i] = 1
            solve(depth + 1, K)

            ans.pop()
            visited[i] = 0
        elif i > ans[-1]:
            ans.append(i)
            visited[i] = 1
            solve(depth+1, K)

            ans.pop()
            visited[i] = 0

while 1:
    K, *S = map(int, sys.stdin.readline().split())
    if K == 0:
        break
    visited = [0] * 50
    ans = []

    solve(0, K)
    print()

 

해설

• N과 M 시리즈 문제들을 풀어봤다면, 쉽게 풀 수 있다.
• 밑의 링크는 N과 M 문제들의 풀이다.
• https://ryuwc.tistory.com/87
• 재귀를 통해 순열을 만들어 출력한다.

 

---

풀이 2 itertools 라이브러리 사용

import sys
from itertools import combinations
while 1:
    K, *S = map(int, sys.stdin.readline().split())
    if K == 0:
        break
    ans = combinations(S, 6)
    for line in ans:
        print(*line)
    print()

 

해설

• itertools의 combinations를 사용하여 풀었다.
• itertools는 순열과 조합에 대한 라이브러리이다.
• 밑의 링크는 itertools 사용법에 대한 링크다.
• https://ryuwc.tistory.com/90

 

풀이 [자바]

import java.io.*;
import java.util.*;

public class Main {
    public static int [] nums;
    public static int n, r;
    public static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        while (true) {
            StringTokenizer st = new StringTokenizer(bf.readLine());
            n = Integer.parseInt(st.nextToken());
            if (n == 0) break;

            nums = new int[n];
            for (int i = 0; i < n; i++) {
                nums[i] = Integer.parseInt(st.nextToken());
            }

            comb(6, new int[6], 0);
            sb.append("\n");
        }
        System.out.println(sb);
    }
    public static void comb(int r, int[] lotto, int start) {
        if (r == 0) {
            for (int i : lotto) {
                sb.append(i).append(" ");
            }
            sb.append("\n");
            return;
        }

        for (int i = start; i < nums.length; i++) {
            lotto[lotto.length-r] = nums[i];
            comb(r-1, lotto, i+1);
        }
    }
}