인프런 커뮤니티 질문&답변

def DFS(x, l, r):
    if x == k:
        if tmp[abs(l - r)] == 0:
            tmp[abs(l - r)] = 1

    else:
        DFS(x + 1, l, r)
        DFS(x + 1, l + a[x], r)
        DFS(x + 1, l, r + a[x])


k = int(input())
a = list(map(int, input().split()))
tmp = [0] * (sum(a) + 1)
DFS(0, 0, 0)
count = 0
for x in tmp:
    if x == 0:
        count += 1
print(count)

 

저는 이런식으로 리스트 만들고 그 값에 해당하는 값을 1로 만들어서 푸는 방식으로 코드를 짰습니다.

채첨 프로그램으로는 100점이 나왔지만 list보다는 set를 사용하는게 시간복잡도상 좋다고 들었습니다

인터넷 검색해보니까 set 과 list 둘다 n번쨰에 element 할당이 O(1)었습니다

제코드랑 선생님의 코드랑 비교하면 set쪽이 더 빠를까요??

이런 문제를 풀떄는 list보다 set을 쓰는게 더 좋을까요??