[백준 10815 파이썬] - 숫자 카드

📌 문제

💯 정답

• 방법 1. 시간초과..

import sys
input = sys.stdin.readline

n = int(input())
card = list(map(int, input().split()))
m = int(input())
card2 = list(map(int, input().split()))

for i in range(m):
    if card2[i] in card:
        print(1, end=" ")
    else:
        print(0, end=" ")

• 방법 2. 성공!!

import sys
input = sys.stdin.readline

n = int(input())
card = set(map(int, input().split()))
m = int(input())
card2 = list(map(int, input().split()))

for i in card2:
    if i in card:
        print(1, end=" ")
    else:
        print(0, end=" ")

# list에서 in 수행시 모든 요소를 처음부터 검사하면서 찾는 원소가 있는지 확인하지만,
# set은 해시로 구현되어 있어 x in set 이 x in list보다 일반적으로 더 빨리 동작하게 된다.

📝 설명

• 두 코드 다 테스트케이스 실행시 성공이였으나 백준에 제출하니 방법 1.은 시간초과가 떴다.

• card 입력받을떼 list가 아닌 set을 사용하니 해결이 되었는데,
  in 수행시 list보다 set이 더 빨리 동작하게 된다는 것이었다.
  
• in 수행 시 모든 요소를 처음부터 검사하면서 원소를 찾는 list 는 O(n)의 시간복잡도를 가지고,
  해시로 구현된 set은 최소 O(1)의 시간복잡도를 가져 일반적으로 더 빨리 동작하기 때문이다.