[Python] 백준 1920번 수 찾기

[Python] 백준 1920번 수 찾기

https://www.acmicpc.net/problem/1920

문제

코드

import sys
n = int(sys.stdin.readline())
n_list = set(map(int,sys.stdin.readline().split()))
m = int(sys.stdin.readline())
m_list = list(map(int,sys.stdin.readline().split()))
for x in m_list:
    if x in n_list:
        print(1)
    else:
        print(0)

리뷰

크게 2가지 풀이 방법이 존재한다.

1. 이진 탐색(이분 탐색) 활용

2. 집합 자료형 활용

1번의 경우 이진 탐색 개념은 알고 있었으나 지금까지 문제를 풀면서 활용해본 적은 없었다. 이진 탐색이 시간 복잡도를 줄이기 위해 사용되는 방법 중 하나라고 한다. 다음에는 1번을 통해 문제를 풀어보자

2번의 경우 내가 원래 작성했던 코드에서 리스트 자료형을 집합 자료형으로 바꾼 결과이다. 리스트에선 시간 초과가 떴지만, 집합에서는 뜨지 않았다.

출처: https://chancoding.tistory.com/43

파이썬에서는 자료형과 메소드, 연산자마다 시간 복잡도가 다르다.

리스트의 경우 삽입, 제거, 탐색, 포함 여부 확인 모두 O(n)의 시간 복잡도를 가지고

집합과 딕셔너리의 경우 삽입, 제거, 탐색, 포함 여부 확인 모두 O(1)의 시간 복잡도를 가진다고 한다.

 

출처: https://debugdaldal.tistory.com/158