[C++][백준] 수 찾기(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안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.
출력
M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.
풀이
최악의 경우 10만개의 데이터에서 수가 존재하는지 탐색하는 과정을 10만번 수행해야 합니다.
이 때 완전 탐색으로 수가 존재하는지 탐색하면 10만 * 10만으로 시간초과가 발생할 수 있습니다.
따라서 완전 탐색이 아닌 이분 탐색으로 시간 복잡도를 줄여야 합니다.
이분탐색의 경우 한번 탐색하는게 걸리는 시간 복잡도를 N에서 logN으로 줄일 수 있기 때문에
총 시간 복잡도를 10만 * log(10만)으로 줄일 수 있습니다.
[표 1] 2의 거듭 제곱
[표 1]을 통해 log(10만)은 대략 17보다 작은 수라고 짐작 할 수 있습니다.
10만 * 17 = 170만번의 연산은 시간 내 충분히 수행 가능합니다.
전체 코드는 아래와 같습니다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N, M;
vector<int> NList;
vector<int> MList;
void init() {
scanf("%d", &N);
for (int i = 0; i < N; i++) {
int val;
scanf("%d", &val);
NList.push_back(val);
}
scanf("%d", &M);
for (int i = 0; i < M; i++) {
int val;
scanf("%d", &val);
MList.push_back(val);
}
sort(NList.begin(), NList.end());
}
bool binary_search(int target) {
if (target < NList[0]) return false;
if (target == NList[0]) return true;
if (target > NList[N - 1]) return false;
if (target == NList[N - 1]) return true;
int l = 0, r = N - 1; // l은 target보다 작다. r은 target보다 크다.
while (l + 1 < r) { // l ~ r 사이에 탐색할 대상이 존재하는 경우
int mid = (l + r) / 2;
if (NList[mid] == target) {
return true;
}
else if (NList[mid] < target) {
l = mid;
}
else if (NList[mid] > target) {
r = mid;
}
}
return false;
}
void solution() {
for (int i = 0; i < M; i++) {
if (binary_search(MList[i])) {
printf("1\n");
}
else {
printf("0\n");
}
}
}
int main() {
init();
solution();
return 0;
}이분 탐색을 수행하기 위해서는 탐색할 데이터가 정렬되어있어야 합니다.
정렬된 데이터에서 첫번째 요소는 가장 작은 데이터, 마지막 요소는 가장 큰 데이터입니다.
1) 따라서 target이 가장 작은 데이터보다 작거나 가장 큰 데이터보다 큰 경우 target은 탐색할 대상에 존재하지 않음을 확정할 수 있습니다.
2) 1번 과정을 통해 L은 target보다 작은 수, R은 target보다 큰 수라는 것을 보장할 수 있습니다.(아래 그림 참조)
따라서 L + 1 < R은 L ~ R 사이에 탐색할 대상이 존재한다고 생각할 수 있으며 이분 탐색을 수행합니다.
Reference