[Silver IV] 수 찾기 - 1920

문제 링크

성능 요약

메모리: 53208 KB, 시간: 156 ms

분류

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

제출 일자

2025년 1월 4일 22:15:53

문제 설명

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

M = int(input())
Mlist = list(map(int, input().split()))
N = int(input())
Nlist = list(map(int, input().split()))

Mdict = {x: True for x in Mlist}

for i in Nlist:
    if i in Mdict:
        print(1)
    else:
        print(0)

정답률이 난이도에 비해 낮게 나온 문젠데 아마 시간초과로 틀린 것 같다 ㅇㅇ..

리스트로 진행했다면 시간초과가 나오는데 문제에서 N = 100,000, M = 100,000이기 때문에
O(N x M) = 10^10이 나온다. 여기서 10^7~10^8만 가능하기에 틀리니까 문제를 안보고 풀면 머리찍힌다. 그래서 딕셔너리로 바꾸면 해결이 가능하다.

딕셔너리(해시 테이블)을 쓴다면 O(N + M)이기 때문에 가능하다. 이해가 안가면 해시테이블의 자료구조를 읽어보면 됨 ㅇㅇ

그리고 이 방법 말고도 정렬 + 이진트리로 풀어도 된다.