문제
N개의 정수가 주어진 집합 A가 있다. M개의 수가 주어질 때, 각 수가 A에 속하는지 여부를 출력한다.
입력
- 첫째 줄: 정수 N (1 이상 100,000 이하)
- 둘째 줄: N개의 정수 (각각 -2^31 이상 2^31 미만)
- 셋째 줄: 정수 M (1 이상 100,000 이하)
- 넷째 줄: M개의 탐색할 정수
출력
- M개의 수에 대해 A에 속하면 1, 아니면 0을 한 줄씩 출력
예제
| 입력 | 출력 |
|---|---|
5 4 1 5 2 3 5 1 3 7 9 5 | 1 1 0 0 1 |
풀이
N개의 수를 정렬한 뒤, M개의 각 수에 대해 이분 탐색으로 존재 여부를 O(log N) 시간에 확인한다.
- N개의 정수를 배열에 저장하고 오름차순 정렬한다.
- M개의 탐색 수를 하나씩 읽어
binarySearch(key)를 호출한다. - 이분 탐색:
l = 0,r = N-1에서 시작해mid값과key를 비교한다.key < arr[mid]이면r = mid - 1,key > arr[mid]이면l = mid + 1key == arr[mid]이면true반환
- 결과를 StringBuilder에 누적해 한 번에 출력한다.
핵심 아이디어: 배열을 정렬하면 이분 탐색으로 O(log N) 조회가 가능하다. M개의 쿼리에 대해 총 O((N + M) log N) 시간이 소요된다. HashSet을 사용하면 O(N + M) 평균 시간도 가능하다.
코드
package com.ssafy.an.day099;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Day78BOJ1920수찾기이분탐색복습 { // 이분탐색
static int N, M;
static int[] arr;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
StringBuilder sb = new StringBuilder();
N = Integer.parseInt(br.readLine());
arr = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++)
arr[i] = Integer.parseInt(st.nextToken());
Arrays.sort(arr);
M = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
for (int i = 0; i < M; i++)
sb.append(binarySerch(Integer.parseInt(st.nextToken())) ? 1 : 0).append("\n");
System.out.println(sb);
br.close();
}
private static boolean binarySerch(int key) {
int l = 0, r = arr.length - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (key < arr[mid])
r = mid - 1;
else if (key > arr[mid])
l = mid + 1;
else
return true;
}
return false;
}
}복잡도
- 시간: O((N + M) log N) — 정렬 O(N log N) + M번의 이분 탐색 O(M log N)
- 공간: O(N) — 집합 배열 저장