[Python] 백준 1920 수 찾기

N = int(input())
Nlist = list(map(int, input().split(' ')))
M = int(input())
Mlist = list(map(int, input().split(' ')))
for i in Mlist:
    if(i in Nlist):
        print(1)
    else:
        print(0)

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

예제 입력

5
4 1 5 2 3
5
1 3 7 9 5

예제 출력

1
1
0
0
1

 

---

첫 번째 코드

N = int(input())
Nlist = list(map(int, input().split(' ')))
M = int(input())
Mlist = list(map(int, input().split(' ')))
for i in Mlist:
    if(i in Nlist):
        print(1)
    else:
        print(0)

 

결과

시간초과

 

두 번째 코드

N = int(input())
Nlist = set(map(int, input().split(' ')))
M = int(input())
Mlist = list(map(int, input().split(' ')))
for i in Mlist:
    if(i in Nlist):
        print(1)
    else:
        print(0)

 

결과

성공

 

코멘트

파이썬의 자료형과 그와 관련된 메소드의 시간 복잡도에 대해서

조사해볼 수 있었던 아주 귀중한 문제였다!

 

리스트의 in 연산자를 이용한 포함 여부의 시간 복잡도는 O(n)이고,

집합의 in 연산자를 이용한 포함 여부 시간 복잡도는 O(1)dlek.

 

즉, 탐색만 하는 경우에는 집합 자료형을 이용하는 것이 시간복잡도 측면에서

훨씬 더 효율적으로 해결할 수 있는 방법인 것이다!

 

파이썬의 자료형과 관련된 시간복잡도는 포스팅할 계획이다.