[알고리즘 / 백준] 6603 - 로또

 

문제는 위와 같으며 49 가지 수 중 6개의 수만을 고르는 문제이기 때문에 주어지는 수의 크기가 크지 않고 오름차순으로 주어지기 때문에 각 자리에 올 수 있는 수를 특정하고 그 수의 다음 수부터 다음 자리에 올 수 있도록 계속 반복하여 재귀 함수를 호출하다 6개의 수가 결정되면 return 하는 방식으로 문제를 해결하였습니다.

 

파이썬 코드는 다음과 같습니다.

from sys import stdin
import copy

result = list() # 하나의 케이스의 모든 경우의 수를 담을 리스트


def lotto(nums, selected):
    if len(selected) == 6:
        result.append(copy.deepcopy(selected)) # 6개의 수가 모두 선택된 경우 해당 경우를 result 리스트에 추가
        return

    for i in range(len(nums)):
        selected.append(nums[i]) # 숫자를 하나 뽑아 선택된 리스트에 추가하고
        lotto(nums[(i + 1):], selected) # 그 숫자 이후 리스트를 다시 반복
        selected.pop() # 해당 자리 수의 숫자를 빼기


while True:
    result.clear()
    inputs = list(map(int, stdin.readline().split()))

	# 입력이 0인 경우 종료
    if len(inputs) == 1 and inputs[0] == 0:
        break

    k = inputs[0]
    s = inputs[1:]

    lotto(s, [])

    for r in result:
        print(" ".join(str(n) for n in r))

    print()

 

자바 코드는 다음과 같습니다. 자바의 경우는 배열을 자르고 넘기는 것이 조금 번거로워서 각 자리에 들어갈 수 있는 수의 시작 인덱스와 끝 인덱스를 사용하여 문제를 해결하였습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        while (true) {
            sb.setLength(0);
            int[] inputs = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

            if (inputs.length == 1 && inputs[0] == 0) {
                break;
            }

            int[] nums = new int[inputs.length - 1];
            System.arraycopy(inputs, 1, nums, 0, nums.length);

            lotto(nums, 0, nums.length - 5, new ArrayList());

            System.out.println(sb);
        }
    }

    private static void lotto(int[] nums, int start, int end,  ArrayList<Integer> selected) {
        if (selected.size() == 6) {
            for (int i = 0; i < 5; i++) {
                sb.append(selected.get(i)).append(" ");
            }
            sb.append(selected.get(5)).append("\n");
            return;
        }

        for (int i = start; i < end; i++) {
            if (i < nums.length) {
                selected.add(nums[i]);
                lotto(nums, i + 1, i + (nums.length - 5) + 1, selected);
                selected.remove(selected.size() - 1);
            }
        }
    }
}