[백준][Silver IV] 수 찾기 - 1920번 파이썬 문제 풀이

 

문제 링크

성능 요약

메모리: 50796 KB, 시간: 152 ms

분류

이분 탐색, 자료 구조, 해시를 사용한 집합과 맵, 정렬

제출 일자

2024년 9월 10일 19:24:04

문제 설명

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을 출력한다.

 

예제 입력 1 복사

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

예제 출력 1 복사

1
1
0
0
1

<풀이>

 #1920
 
a = int(input())
b = list(map(int,input().split(' ')))

b1 = set(b)
c = int(input())
d = list(map(int,input().split(' ')))

for i in d:
    if i in b1:
        print(1)
    else :
        print(0)

 

 

for i in d:
    if i in b1:

이 부분에서 만약 b1이 b가 된다면 for문안에 b라는 리스트를 쭉 돌면서 if문을 처리하기 때문에 이중for 문의 시간 복잡도와 비슷해진다.  이렇게 풀면 시간초과가 발생해서 문제를 틀리게 된다.

 

그래서 b를 b1인 집합처리를 해버리면 단순히 집합안에서 찾는 경우이기 때문에 시간 복잡도가 줄어들고, 문제를 맞힐 수 있다.