6603 파이썬

6603 파이썬

해당 문제는 itertools 사용하면 정말 쉽게 풀리지만, 백트래킹으로 풀어보는데 도움이 된 문제였다.

import sys 
idx = False 

def generate_num(lst,total_cnt,pre,result):
    if total_cnt == 6:
        print(* result)
        return

    for i in range(pre,len(lst)): #현재까지 iterate한 number 이후부터 추가로 넣어준다. 
        result.append(lst[i])
        generate_num(lst,total_cnt+1,i+1,result)
        result.pop() # 트리로 생각하면 왼쪽 child에 접근 후, 이를 빼고 right child를 넣어주는 과정이라고 생가하면 된다.

while True:
    input_string = list(map(int,sys.stdin.readline().strip().split()))
    if input_string[0] == 0:
        break 
    if idx != False:
        print() # 공백 줄 출력하는 방식 
    else:
        idx = True # 첫번째 입력이 아니면 공백 줄을 출력한다. 
    # print("1",input_string[1:])
    generate_num(input_string[1:], 0,0,[])

처음에는 문자열을 넘겨주는 방식을 쓰느라, set과 list를 사용해서 시간초과가 일어났는데,1. 애초에 backtracking 할 범위를 지정해주고, 2. child node를 추출하고 다른 child node를 넣어주는 방식을 구현하는 것이 주 키 포인트라고 생각한다.