[파이썬] 백준 6603 로또 (조합 combinations)

✅ 백준 문제 링크: 백준 6603번 - 로또

백준 6603 로또

1. 문제 설명

 

독일의 로또는 6개의 숫자를 선택하는 방식이다.

• 주어진 K개의 숫자 중에서 6개를 고르는 모든 조합을 출력하는 문제이다.
• 입력의 마지막 줄에는 0이 주어지며, 이를 입력의 종료 조건으로 사용한다.
• 각 테스트 케이스는 사전순(오름차순)으로 출력해야 한다.

2. 조합(Combination)이란?

 

조합이란, 주어진 n개의 원소 중에서 r개를 선택하는 경우의 수를 의미한다.

순서가 중요하지 않으며, 파이썬에서는 itertools.combinations() 함수를 사용하면 쉽게 구현할 수 있다.

 

📌 조합 예제

from itertools import combinations

numbers = [1, 2, 3, 4]
combi = list(combinations(numbers, 2))  # 4개 중에서 2개를 선택하는 경우의 수
print(combi)

 

🔹 출력:

[(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]

 

3. 문제 해결 방법

1. 첫 번째 수 K와 K개의 수 집합 S에 포함되는 수를 입력받는다.
2. 입력된 K의 수가 0 이면 빠져나간다.
3. 입력된 K를 제거한다.
4. 신규 리스트에 집합 S에 포함되는 수를 복사한다.
5. 복사할 때 파이썬의 조합 combinations 함수를 활용하여 조합의 경우의 수만큼 리스트 담는다.
6. 신규 리스트 값만큼 반복하면서 노출한다.

4. 파이썬 코드 구현

import sys
from itertools import combinations
rtn = []

while True:
    #1.첫번째 수 K 와 K개의 수 집합 S에 포함되는 수를 입력받는다.
    inpL = list(map(int, sys.stdin.readline().rsplit()))
    #2.입력된 K 의 수가 0 이면 빠져나간다.
    if inpL[0] == 0:        
        break
    #3.입력된 K 를 제거한다.
    inpL.pop(0)
    #4.신규 리스트에 집합 S에 포함되는 수를 복사한다.
    #5.복사할 때 파이썬의 조합 combinations 함수를 활용하여 조합의 경우의 수만큼 리스트 담는다. 
    rtn += list(combinations(inpL,6)).copy()
    rtn.append("")
    
#6.신규 리스트만큼 반복하면서 노출한다.    
for i in range(0, len(rtn)-1):
    print(" ".join(map(str, rtn[i])))

 

5. 예제 테스트

 

✔ 입력 예시

7 1 2 3 4 5 6 7
8 1 2 3 5 8 13 21 34
0

 

✔ 출력 예시

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

 

6. 시간 복잡도 분석

• 조합 연산: itertools.combinations(S, 6)는 O(K^6) 복잡도를 가진다.
• 최대 K=12이므로, 최대 경우의 수는 924가지로 연산이 충분히 가능.

✅ itertools.combinations()를 사용하여 간결하고 효율적으로 문제를 해결했다! 🚀