BOJ 1920 수 찾기

태그

자료 구조

정렬

이분 탐색

생성일

2024/12/11 12:11

URL

•

크기가 NNN인 배열에 대해서 MMM개의 수가 있는지 없는지를 판단하는 문제

•

입력1

Plain Text
복사

•

출력1

Plain Text
복사

•

1≤N≤100,0001 ≤ N ≤ 100,0001≤N≤100,000

•

1≤M≤100,0001 ≤ M ≤ 100,0001≤M≤100,000

풀이1 브루트 포스 - O(M⋅N)O(M \cdot N)O(M⋅N)

•

풀이2 이분 탐색 이용 - O((N+M)⋅logN)O((N+M) \cdot logN)O((N+M)⋅logN)

•

풀이3 set 자료구조 이용 - O(N+M)O(N + M)O(N+M)

풀이2 이분 탐색 재귀 (메모리 초과)

풀이2 이분 탐색

풀이3 set 자료구조 이용