💡 풀이방법

파이썬의 라이브러리 중 순열, 조합을 가져와서 풀면 굉장히 짧고 쉽게 풀리지만 코딩 테스트에서는 해당 라이브러리를 허용하지 않을 수 있을 뿐더러 이 문제의 의도는 dfs 재귀를 활용한 브루트 포스이므로 dfs를 이용해 풀었다.

일단 뽑은 번호를 저장하고 추후에 결과로 출력할 배열인 dp를 만들었다. 어차피 번호는 6개니까 dp의 크기도 6으로 했다.

이후 dfs를 구현했는데, 인자를 start와 depth로 주었다. depth는 현재 몇 번째 수를 뽑는 것인지 나타내는 것이다. start는 뽑는 수에 경우의 수가 생기기 시작하는 바로 앞 지점이다. 이게 이해하는데에 오래걸렸는데, 예를 들어 1,2,3,4,5,6,7 중 6개를 사전순으로 뽑을 때 1,2,3,4,5까지 뽑고 6을 뽑을지 7을 뽑을지 선택할 수 있다. 이 때 start의 값이 5가 된다. 그래서 dfs(0,0)을 시작으로 재귀를 쭉 들어가보면 dfs(5,5)가 나오게 되고 for i in range(5,7)에 의해 arr[5]의 값이 마지막 depth에 들어가는 경우와 arr[6]의 값이 마지막 depth에 들어가는 경우가 나온다. 즉 1,2,3,4,5,6과 1,2,3,4,5,7의 경우이다.

📝소스코드

import sys
input = sys.stdin.readline

def dfs(start, depth):
	# 길이가 6이면 숫자를 다 뽑은 것이므로 출력하고 return
    if depth == 6:
        print(*dp)
        return
    # 갈림길 start에서 경우의 수를 dfs 재귀를 통해 구현
    for i in range(start, len(arr)):
        dp[depth] = arr[i]
        dfs(i+1, depth+1)
    
while True:
    dp = [0]*6
    arr = list(map(int, input().split()))
    K = arr[0]
    if K == 0:
        break
    arr = arr[1:]
    dfs(0, 0)
    print()