[BOJ/C++] 수 찾기(1920번)

1. 문제 개요

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

1920번: 수 찾기

1-1. 설명

N개의 정수 A[1], A[2], ..., A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. 첫줄에 자연수 N이 주어지고 다음 줄에 N개의 정수가 주어진다. 다음 줄에는 M이 주어지고, 그 다음줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 

1-2. 제한 사항

 - N과 M은 1이상 100,000이하

 - 모든 정수의 범위는 -2^31보다 크거나 같고 2^31보다 작음

---

2. 구현

2-1. 설명

이진 탐색 알고리즘을 이용한다. 우선 N개의 정수가 저장된 리스트를 먼저 퀵정렬로 정렬을 진행한 다음 이진 탐색 알고리즘을 사용했다. 자세한 이진 탐색 알고리즘은 이전 게시글에 작성했으니 확인하면 된다. C++의 시간을 최대한으로 줄이기 위해 ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);을 앞에 포함시켜주고 endl을 사용하지 않았다. 메인말고 따로 함수를 작성해서 코드를 실행시키니, 자꾸 시간 초과가 떠서 메인에 모든 내용을 넣어주었다. 시간초과가 뜨는 이유가 앞선 이유인지는 정확하지 않지만, 함수에 있는 내용을 메인에 모두 옮기니 시간초과가 뜨지 않았다.

2-2. 코드

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

using namespace std;


int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M, input;
	vector<int> numbers1;

	cin >> N;
	for (int i = 0; i < N; i++) { // N개의 정수 저장
		cin >> input;
		numbers1.push_back(input);
	}
	sort(numbers1.begin(), numbers1.end()); // 오름차순으로 정렬

	cin >> M;
	for (int i = 0; i < M; i++) {
		cin >> input;
		int first = 0, last = N - 1;
		while (first <= last) { // 이진 탐색 알고리즘
			int mid = (first + last) / 2;
			if (input == numbers1[mid]) {
				cout << "1\n";
				break;
			}
			else if (input < numbers1[mid]) last = mid - 1;
			else first = mid + 1;
		}
		if (first > last) cout << "0\n";
	}
	return 0;
}