BOJ 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안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -2^31 보다 크거나 같고 2^31보다 작다.

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

풀이

N개의 수 중에서 어떤 값이 있는지만 여러 번 확인하는 문제라서, 수열을 정렬한 뒤 질의마다 이분 탐색을 하면 된다. 한 번 정렬해 두면 각 질의를 빠르게 처리할 수 있다.

코드는 질의값마다 배열 가운데를 기준으로 범위를 좁혀 가며 찾는다. 마지막에 정확히 같은 값을 만나면 1, 끝까지 못 찾으면 0을 출력하는 단순한 membership query 구조다.

코드

#include <iostream>
#include <algorithm>
using namespace std;
 
int A[100001] = {};
 
void binary_search(int n, int start, int end) {
 
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
 
	if (start > end) {
		cout << 0 << '\n';
		return;
	}
		
	int mid = (start + end) / 2;
	
	if (A[mid] == n) {
		cout << 1 << '\n';
		return;
	}
	else if (A[mid] > n) 
		return binary_search(n, start, mid - 1);
	else 
		return binary_search(n, mid + 1, end);
}
 
int main() {
 
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int N;
	cin >> N;
 
	int n;
	for (int i = 0; i < N; i++) {
		cin >> n;
		A[i] = n;
	}
 
	sort(A, A + N);
 
	int M;
	cin >> M;
	
	int m;
	for (int j = 0; j < M; j++) {
		cin >> m;
		binary_search(m, 0, N - 1);
	}
 
	return 0;
}

복잡도

시간 복잡도: 배열 정렬 $O(N \log N)$ 뒤 $M$ 개 질의를 이분 탐색으로 처리하므로 $O(N \log N + M \log N)$ 이다.
공간 복잡도: 기준 배열을 저장하므로 $O(N)$ 이다.

마무리

여러 값의 존재 여부를 반복해서 묻는 문제는 미리 정렬해 둔 뒤 탐색 비용을 줄이는 것이 핵심이다. 한 번 정렬하면 각 질의는 이분 탐색으로 빠르게 판정할 수 있다.

문제#

입력#

출력#

풀이#

코드#

복잡도#

마무리#

문제

입력

출력

풀이

코드

복잡도

마무리