[BOJ] 1920번: 수 찾기

문제 링크

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

접근한 방식

만약 순차탐색으로 해결하려면 M개의 수를 차례로 방문하면서 해당 수가 N개의 정수중에 있는지 순차적으로 탐색해야 한다. 이럴경우 시간복잡도가 O(N * M)가 되기 때문에 N과 M이 둘다 100000이라면 10000000000 이라는 시간이 걸리기 때문에 시간 초과가 발생한다.

하지만 이분탐색으로 해결한다면,

A 배열을 정렬하는 시간(C++ sort() 기준): O(NlogN)
이분 탐색 시간(C++ binary_search() 기준): O(logN)
M개의 수를 차례대로 방문하는 시간: O(M)

이므로
총 시간복잡도는 O(NlogN + MlogN) 이 된다.
따라서 N과 M이 전부 100000 이어도 약 1000000 이라는 시간밖에 걸리지 않기 때문에 시간 초과가 뜨지 않는다.

코드

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N, M;
vector<int> A, B;

int main() {
	scanf("%d", &N);
	A.resize(N);

	for (int i = 0; i < N; i++)
		scanf("%d", &A[i]);

	// 이분 탐색을 위해 정렬
	sort(A.begin(), A.end());

	scanf("%d", &M);
	B.resize(M);

	for (int i = 0; i < M; i++)
		scanf("%d", &B[i]);

	// 이분 탐색 결과 출력
	for (int i = 0; i < M; i++)
		printf("%d\n", binary_search(A.begin(), A.end(), B[i]));

	return 0;
}