ndb796/python-for-coding-test

7_7.py 답안 예시에서 set 사용 이유가 궁금합니다.

kim-jinseop opened this issue · 1 comments

kim-jinseop commented 
n = int(input())
array_n = list(map(int,input().split()))  # 1
m = int(input())
array_m = list(map(int,input().split()))

for i in array_m :
    if i in array_n :
        print("yes",end=" ")
    else : 
        print("no",end=" ")

print(array_n)

책에서는 #1 번 부분에 set으로 집합 형태를 만들었는데, 그냥 list 형태에서 if ~ in ~ 문법을 사용하면 안되는건가요?
서로 어떤점이 다른건지 잘모르겠습니다.

SeungrokYoon commented

Set()자료구조와 List 자료구조에서 원소 탐색을 진행할 때의 시간 복잡도에는 차이가 있습니다.
리스트에서 if~ in 문법을 사용할 경우, 하나하나 원소를 순회하기 때문에 시간 복잡도가 O(n)인 반면, Set 자료구조에서 원소를 찾을 때는 시간 복잡도가 대개 O(1)입니다. Set은 해시맵으로 값이 저장되기 때문이죠.
이 차이로 인해 교재에서는 Set을 사용하지 않았나 싶습니다.

  • 👍1