백준 알고리즘 파이썬(Python) 6603번 로또

---

 

풀이 1

itertools의 permutation을 사용한 풀이이다.

우선 arr에 입력값을 받고 arr의 첫 번째 원소를 pop(0)을 통해 빼준다.

그리고 permutation을 통해 모든 경우의 수를 arr_p에 넣어주고 그중 정렬되어있는 리스트들만 print 해주면 된다.

하지만 permutaion을 사용하였기 때문에 시간복잡도가  O(n!)여서 아슬아슬하게 통과하게 된다.

import sys
from itertools import permutations
input = sys.stdin.readline

while True:
    arr = list(map(int, input().split()))
    n = arr.pop(0)
    arr_p = list(permutations(arr, 6))
    for case in arr_p:
        case = list(case)
        if case != sorted(case):
            continue
        elif case == sorted(case):
            print(*case)
            continue
    print()
    if n == 0:
        break

 

 

---

풀이 2

DFS를 이용한 풀이이다. (풀이 출처 : 링크)

 

8 1 2 3 5 8 13 21 34 를 입력받았다면

del arr[0]을 통해 첫 번째를 삭제해주고 arr에는  1, 2, 3, 5, 8, 13, 21, 34가 담긴다.

dfs함수를 처음 쓰게 되면

dp배열에는 차례대로 1, 2, 3, 5, 8, 13이 담기게 된다.

depth가 6이기때문에 출력을 해주고 return 하여 이전 함수로 돌아가게 된다.

for 문의 i는 증가한 상태이므로 1, 2, 3, 5, 8, 21이 담기게 된다.

이렇게 순서대로 dfs를 이용하여 풀어준다. 

이렇게 풀 경우 시간이 풀이 1보다 5배정도 빨라지는 것을 확인할 수 있었다.

import sys
input = sys.stdin.readline

dp = [0 for i in range(13)]

def dfs(start, depth):
    if depth == 6:
        for i in range(6):
            print(dp[i], end=' ')
        print()
        return
    for i in range(start, len(arr)):
        dp[depth] = arr[i]
        dfs(i + 1, depth + 1)

while True:
    arr = list(map(int, input().split()))
    if arr[0] == 0:
        break
    del arr[0]
    dfs(0, 0)
    print()