[BOJ-6603 로또] 브루트포스(조합) (python)

문제조건

k개 수 중에 6개를 고른다. (조합)

핵심개념

• 파이썬 itertools.combinations 라이브러리를 사용하거나
• 재귀함수를 이용하거나
• next_permutations 함수를 구현하여 사용하는 방법이 있다.

코드

(1) 파이썬 itertools.combinations 라이브러리 사용하는 방법

from itertools import combinations

while True:
    num = list(map(int, input().split()))
    if num[0] == 0:
        break

	#입력받은 수에서 (맨 왼쪽 제외) 6개를 선택하는 경우
    for i in combinations(num[1:], 6):
        print(' '.join(map(str, i)))

    print()

(2) 재귀함수 사용하는 방법

lotto = [0] * 6

def go(idx, start, n, m):
    if idx == 6:
        print(' '.join(map(str, lotto)))
        return

    for i in range(start, len(n)):
        lotto[idx] = n[i]
        go(idx + 1, i + 1, n, m)


while True:
    num = list(map(int, input().split()))
    if num[0] == 0:
        break
    go(0, 0, num[1:], 6)
    print()

(3) next_permutations 함수를 구현하여 사용하는 방법

def next_permutations(a):
    # i 찾기
    i = len(a) - 1
    while i > 0 and a[i - 1] >= a[i]:
        i -= 1

    # 마지막 순열인 경우 return 하기 (내림차순)
    if i == 0:
        return False

    # j 찾기
    j = len(a) - 1
    while i - 1 < j and a[i - 1] >= a[j]:
        j -= 1

    # 바꾸기
    a[i - 1], a[j] = a[j], a[i - 1]

    # 내림차순으로 정렬하기
    j = len(a) - 1
    while i < j:
        a[i], a[j] = a[j], a[i]
        i += 1
        j -= 1

    return True


while True:
    num = list(map(int, input().split()))
    if num.pop(0) == 0:
        break

    # 0은 로또로 뽑히는 경우, 1은 로또로 안 뽑히는 경우
    arr = [0] * 6 + [1] * (len(num) - 6)

    print(' '.join(map(str, num[0:6])))

    while next_permutations(arr):
        for i in range(len(num)):
            if arr[i] == 0:
                print(num[i], end=' ')
        print()
    print()