[백준] [Python] 6603번 로또 - 백트래킹

www.acmicpc.net/problem/6603

6603번: 로또

 

 

 

Python

import sys

arr = []
visit = []
n=0
result = [[]]

def back(k):
    global visit
    
    if k>=6:
        temp = [ y for y in visit if y!='']
        # in 키워드는 앞에서부터 탐색
        # 뒤에서부터 탐색하여 시간 단축
        for i in range(len(result)-1,-1,-1):
            if temp == result[i]:
                return
            
        print(' '.join(temp))
        result.append(temp)
        return
    
    for i in range(k,(n)):
        # 해당 원소를 사용한 적이 있다면 패스
        if arr[i] == visit[i]:
            continue
         
        visit[i] = arr[i]
        back(k+1)
        visit[i] = ''
        

while True:
    x = sys.stdin.readline().rstrip()
    if x == '0':
        break
    arr = x.split()
    n = int(arr[0])
    visit = ['']*n
    arr = arr[1:]

    back(0)
    print()

 

 

짧은 풀이

백트래킹에서 중복 여부를 검사할 때 전체 리스트를 살펴보는 것이 아니라

visit 리스트에 해당 원소가 표시되어있는지 확인함으로써 O(1)로 시간 단축