[Baekjoon/백준] 1920번: 수 찾기(C/C++)

단계별로 풀어보기 21단계(이분 탐색) 1번 문제

https://www.acmicpc.net/step/29

이분 탐색 단계

---

백준 1920번: 수 찾기

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

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을 출력한다.

---

접근 방법

이번 문제는 자연수 N을 입력받고 이후 N개의 정수를 입력받아 그 정수들이 담긴 배열 A를 만든 뒤, 자연수 M을 입력받아서 M개의 정수가 배열 A에 있는지 확인해 있으면 1을, 없으면 0을 출력하는 문제다.

일단 그냥 배열 A를 처음부터 끝까지 탐색하기에는 배열 크기 N과 찾을 숫자 개수 M의 범위가 커서 시간 초과가 발생할 것이다. 따라서 이분 탐색을 통해서 문제를 풀이해야한다.

이분 탐색은 정렬된 배열의 중앙값부터 시작해서 중앙 값보다 작다면 배열의 왼쪽을, 크다면 배열의 오른쪽을 탐색하는 것이다. 즉, 배열을 입력받은 뒤에는 정렬해야하며, 이후 해당 배열의 중앙 값을 기준으로 찾으려는 값보다 큰지 작은지 확인해 더 가까운 수로 접근하는 반복문과 함수를 만들면 문제를 해결할 수 있다.

---

코드

#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 100000

int A[MAX];

int check(int N, int num) {
	int mid, start = 0, end = N - 1;
	
	while (end >= start) {
		mid = (start + end) / 2;
		if (A[mid] == num)
			return 1;
		else if (A[mid] > num)
			end = mid - 1;
		else
			start = mid + 1;
	}

	return 0;
}

int main(int argc, char *argv[]) {
	ios_base::sync_with_stdio(0); cin.tie(0);

	int N, M, num;

	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> A[i];

	sort(A, A + N);

	cin >> M;
	for (int i = 0; i < M; i++) {
		cin >> num;
		cout << check(N, num) << "\n";
	}

	return 0;
}

---

결과

백준 제출 결과

문제 풀이 자체는 빠르게 했지만 endl 사용과 ios_base::sync_with_stdio(0); cin.tie(0);를 쓰지 않아서 시간 초과가 발생했다.