백준 - 6603번 로또 python 문제풀이 [Hellfer]

https://www.acmicpc.net/problem/6603

6603번: 로또

🔷 알고리즘 분류 - 백트래킹, 재귀, 조합론  난이도 - 실버 2

🔶 첫 번째 문제풀이 - 백트래킹(재귀함수)을 이용한 풀이

# 재귀 함수 정의
def solve(start, depth):
    # depth가 6이 되면 (즉, 6개의 로또 번호를 선택하면) 그 선택된 번호들을 출력
    if depth == 6:
        for i in range(6):
            print(number[i], end=' ')
        print()
        return
    # start부터 시작하여 로또 번호 리스트의 모든 번호에 대해 수행
    for i in range(start, len(lotto)):
        # 현재 depth의 로또 번호를 선택
        number[depth] = lotto[i]
        # 다음 depth의 값을 결정하기 위해 solve 함수를 재귀적으로 호출
        solve(i + 1, depth + 1)

# 선택된 로또 번호들을 저장할 리스트
number = [0 for _ in range(13)]

# 무한 루프
while True:
    # 사용자로부터 로또 번호를 입력받음
    lotto = list(map(int, input().split()))
    # 첫 번째 숫자가 0이면 루프를 종료
    if lotto[0] == 0:
        break
    # 첫 번째 숫자(로또 번호의 개수)를 삭제
    del lotto[0]
    # 로또 번호를 선택하는 solve 함수를 호출
    solve(0, 0)
    # 한 줄 띄우기
    print()

🔶 코드 풀이

 # start부터 시작하여 로또 번호 리스트의 모든 번호에 대해 수행
    for i in range(start, len(lotto)):
        # 현재 depth의 로또 번호를 선택
        number[depth] = lotto[i]
        # 다음 depth의 값을 결정하기 위해 solve 함수를 재귀적으로 호출
        solve(i + 1, depth + 1)

 

 

이 코드의 예시를 들어 설명드리겠습니다. 먼저, 리스트 lotto = [1, 2, 3, 4, 5, 6, 7]이 주어졌다고 가정해 봅시다. number는 선택한 번호들을 저장하는 리스트입니다.

start는 0이고 depth는 0입니다. for 루프는 start부터 시작하여 lotto의 길이까지 반복합니다. 첫 번째 반복에서 i는 0입니다. number [depth] 즉 number [0]에 lotto [i] 즉 lotto [0]을 저장합니다. 이제 number는 [1, 0, 0, 0, 0, 0, 0]입니다.

그리고 solve(i + 1, depth + 1) 즉 solve(1, 1)을 호출합니다. 이제 start는 1이고 depth는 1입니다. 이 for 루프도 start부터 시작하여 lotto의 길이까지 반복합니다. 첫 번째 반복에서 i는 1입니다. number [depth] 즉 number [1]에 lotto [i] 즉 lotto [1]을 저장합니다. 이제 number는 [1, 2, 0, 0, 0, 0, 0]입니다.

이런 식으로 계속해서 solve 함수를 재귀적으로 호출하며 번호를 선택합니다. depth가 6이면 6개의 번호를 모두 선택한 것이므로 선택한 번호들을 출력하고 재귀를 종료합니다.

이 과정을 통해 lotto에서 6개의 번호를 선택하는 모든 경우의 수를 구할 수 있습니다.

 

 del lotto[0]
    # 로또 번호를 선택하는 solve 함수를 호출
    solve(0, 0)
    # 한 줄 띄우기

 

 

del lotto [0]는 리스트 lotto의 첫 번째 요소를 삭제하는 코드입니다. 이는 입력받은 lotto 리스트에서 첫 번째 요소가 로또 번호의 개수를 나타내므로, 실제 로또 번호만을 남기기 위해 사용됩니다.

solve(0, 0)은 solve 함수를 호출하는 코드입니다. 여기서 0, 0은 각각 start와 depth의 초기값을 나타냅니다. start는 선택을 시작할 로또 번호의 인덱스를, depth는 현재까지 선택한 로또 번호의 개수를 나타냅니다.

예를 들어, lotto = [7, 1, 2, 3, 4, 5, 6, 7]로 입력을 받았다고 가정해 봅시다. 이때 lotto [0]은 로또 번호의 개수인 7입니다. 따라서 del lotto [0]을 실행하면 lotto는 [1, 2, 3, 4, 5, 6, 7]이 됩니다.

그리고 solve(0, 0)을 호출합니다. 이는 로또 번호 리스트 lotto의 첫 번째 인덱스부터 시작하여, 아직 어떤 번호도 선택하지 않았음을 의미합니다.

이후 solve 함수는 재귀적으로 로또 번호를 선택하며, depth가 6이 되면 (즉, 6개의 로또 번호를 선택하면) 그 선택된 번호들을 출력합니다. 이 과정은 로또 번호 리스트의 모든 번호에 대해 수행되어, 6개의 로또 번호를 선택하는 모든 경우의 수를 출력하게 됩니다.

🔶 두 번째 문제풀이 - 조합론을 이용한 풀이

# itertools 모듈의 combinations 함수를 사용하기 위해 import
from itertools import combinations

# 무한 루프
while True:
    # 사용자로부터 로또 번호를 입력받음
    lotto = list(map(int, input().split()))
    # 첫 번째 숫자가 0이면 루프를 종료
    if lotto[0] == 0:
        break
    # 첫 번째 숫자(로또 번호의 개수)를 삭제
    del lotto[0]
    # itertools의 combinations 함수를 사용해서 로또 번호 리스트에서 6개를 선택하는 모든 조합을 생성
    for comb in list(combinations(lotto, 6)):
        # 각 조합을 출력. 각 번호는 공백으로 구분되며, 번호는 문자열로 변환하여 출력
        print(' '.join(map(str, comb)))
    # 한 줄 띄우기
    print()

 

 

이 코드는 파이썬의 itertools 모듈의 combinations 함수를 활용하여 문제를 해결합니다. 

combinations 함수는 주어진 리스트에서 지정된 개수의 요소를 선택하는 모든 경우의 수를 구해줍니다. 

이 함수를 활용하면 복잡한 백트래킹 과정 없이도 해결할 수 있습니다.

 

🤗파이팅입니다~ 여러분!!🤗