https://www.acmicpc.net/problem/6603
1. itertools(combinations)
처음에는 조합 문제라고 생각하여 itertools 라이브러리를 생각했다. 문제의 조건을 보고 시간복잡도를 계산해보니 제한 시간(1초) 내에 풀 수 있겠다고 판단하여 라이브러리를 사용했다.
from itertools import combinations
import sys
input = sys.stdin.readline
while True:
li = list(map(int, input().split()))
if li[0] == 0: # k가 0이면 프로그램 종료
break
k = li[0]
s = li[1:]
for li in list(combinations(s, 6)): # 집합 s에서 6개의 수를 뽑는 조합을 리스트로 변환하여 저장
print(*li) # 각 리스트, 한 칸씩 띄어서 출력
print()
2. 백트래킹
다른 풀이를 보니 라이브러리를 사용하지 않고, 백트래킹을 사용해서 풀었다.
import sys
input = sys.stdin.readline
def dfs(depth, idx):
if depth == 6: # 뽑은 숫자의 수가 6개가 되면 출력
print(*lotto)
for i in range(idx, k): # 현재 인덱스의 숫자에서부터 마지막 인덱스의 숫자까지 반복
lotto.append(s[i]) # 리스트에 숫자 저장
dfs(depth + 1, i + 1) # 뽑은 숫자의 수와 인덱스를 1씩 증가시켜 재귀호출
lotto.pop() # 함수가 반환되면 리스트에 있던 마지막 숫자 제거
while True:
li = list(map(int, input().split()))
if li[0] == 0:
break
k = li[0]
s = li[1:]
lotto = [] # 뽑은 숫자 저장할 리스트
dfs(0, 0)
print()위의 코드에서 for i in range(idx, k): 이 부분이 이 코드의 핵심이라고 생각한다.
숫자를 정답 리스트(lotto)에 넣었다가 다른 숫자 조합을 위해 마지막 숫자를 제거(pop)했을 때, 이전에 넣었던 숫자를 다시 넣지 않기 위해서 어떻게 하면 좋을지 생각했다.
그 답은 해당 코드에 있다.
for문의 범위를 현재 인덱스의 숫자(s[idx])부터 마지막 인덱스의 숫자(s[k-1])까지 설정했기 때문에, 마지막 숫자(s[i])를 제거해도 for문의 특성(i++)으로 인해 다음 숫자로 자동으로 넘어가게 되는 것이다.
* 실제 시험에서는 라이브러리 사용을 금지하는 경우도 있기 때문에 알아두는 것을 추천한다.