[백준] 1920번 수 찾기 (Python)

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

📌 문제

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초 라는 것인데요 !!

그렇기 때문에 일반적인 리스트 조회 방식(O(N))으로 풀면 시간초과가 나게 됩니다

(저도 처음에 리스트에서 in 연산을 사용했는데 바로 시간초과가 나더라구요 ㅎㅎ)

알고리즘 분류에 해시를 사용한 집합과 맵 이 있는 걸 확인하고 딕셔너리를 활용해 평균 O(1) 시간 복잡도로 문제를 풀었습니다!!

---

📌 코드

import sys
input = sys.stdin.readline

N = int(input())
numbers = dict.fromkeys(map(int, input().split()), True)

M = int(input())
munmbers = list(map(int, input().split()))

for mumber in munmbers:
    print(int(mumber in numbers))

 

✅ dict.fromkeys(iterable, value)를 활용하면 키를 빠르게 생성할 수 있고,
✅ in 연산을 사용해도 O(1) 평균 복잡도로 빠르게 확인할 수 있습니다!