[백준] 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이 하나 주어진다.

출력

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

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

예제 입력 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

내 코드

# 없음

chatGPT

이 문제는 주어진 집합에서 6개의 숫자를 조합해 출력하는 방식입니다. 조합(combination)을 구하는 문제이므로, Python의 itertools.combinations를 활용하면 간단하게 해결할 수 있습니다. 이 방식은 주어진 숫자들이 이미 오름차순으로 정렬되어 있기 때문에 별도의 정렬 작업 없이 바로 사전순으로 조합을 출력할 수 있습니다.

아래는 이 문제에 적합한 코드와 설명입니다.

from itertools import combinations

while True:
    # 입력 받기
    input_data = list(map(int, input().split()))
    k = input_data[0]  # 첫 번째 수는 k
    if k == 0:  # 0이 들어오면 종료
        break
    S = input_data[1:]  # 나머지 숫자들은 집합 S

	  for comb in combinations(S, 6):
        print(*comb)
    print()  # 테스트 케이스 사이에 빈 줄 출력

설명

1. 입력 처리: 먼저 각 줄을 리스트로 변환하여 k 값과 S 집합을 나누어 처리합니다. k가 0이면 반복문을 종료합니다.
2. 조합 생성: itertools.combinations(S, 6)를 통해 집합 S에서 6개씩 뽑은 모든 조합을 생성합니다.
3. 출력: print(*comb)는 comb 안의 원소들을 하나씩 꺼내어 공백을 두고 한 줄에 출력합니다. print()로 빈 줄을 출력하여 각 테스트 케이스 사이에 공백을 추가합니다.

주의사항

이 코드는 모든 조합을 메모리에 저장하는 것이 아니라, 하나씩 생성하면서 처리하므로 메모리 효율이 높습니다. 또한 itertools.combinations는 시간 복잡도가 최적화된 함수이기 때문에, 직접 조합을 구현하는 것보다 빠르고 간편하게 조합을 구할 수 있습니다.

부가질문

이 문제를 itertools 를 이용하지 않고 직접 구현하는 방법은?

itertools.combinations를 사용하지 않고 직접 구현하려면, 재귀 함수를 통해 조합을 생성하는 방식이 일반적입니다. 재귀 함수는 각 위치에서 숫자를 선택하거나 건너뛰며 모든 가능한 조합을 만들어냅니다.

이 문제에서는 집합 S에서 숫자 6개를 선택하는 모든 조합을 출력해야 하므로, 다음과 같이 재귀 함수를 이용해 직접 구현할 수 있습니다:

def find_combinations(S, combination, start):
    # 조합이 6개의 숫자로 채워지면 출력
    if len(combination) == 6:
        print(" ".join(map(str, combination)))
        return

    # S 리스트의 각 숫자를 선택해 조합을 구성
    for i in range(start, len(S)):
        # 현재 숫자를 조합에 추가하고 다음 숫자를 재귀적으로 탐색
        find_combinations(S, combination + [S[i]], i + 1)

while True:
    input_data = list(map(int, input().split()))
    k = input_data[0]
    if k == 0:
        break
    S = input_data[1:]

    # 조합 찾기 시작
    find_combinations(S, [], 0)
    print()  # 테스트 케이스 사이에 빈 줄 출력

설명

1. find_combinations 함수:
   • combination 리스트는 현재 선택한 숫자를 담아 조합을 형성합니다.
   • start는 현재 선택할 수 있는 숫자의 시작 인덱스입니다. 각 재귀 호출에서 선택된 숫자의 다음 인덱스부터만 선택해 중복을 방지합니다.
   • 조합의 길이가 6이 되면 출력합니다.
2. 반복문:
   • 각 숫자를 선택하여 새로운 조합을 만들고, 재귀 호출을 통해 남은 숫자를 선택하는 방식으로 모든 조합을 생성합니다.
3. 출력:
   • 각 테스트 케이스가 끝나면 빈 줄을 출력해 구분합니다.

이 방식은 itertools.combinations와 동일하게 작동하며, 재귀적으로 직접 조합을 구현합니다.

내 생각

1. combinations 를 기억하자. 로또 처럼 중복없는 경우의 수 뽑을 때 사용한다. 사용법: from itertools import combinations
2. 직접 구할땐 재귀 함수를 사용한다. 생각보다 길지않다.
3. 숫자 조합이 생성되는 순서를 직접 작성해보았다. 숫자 제시: 1 2 3 4 5 6 7

[1, 2, 3, 4]
	[1, 2, 3, 4, 5]
		[1, 2, 3, 4, 5, 6]  # 출력
		[1, 2, 3, 4, 5, 7]  # 출력
	[1, 2, 3, 4, 6]
		[1, 2, 3, 4, 6, 7]  # 출력