[백준/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을 출력한다.

예제

---

아이디어

A[N]을 입력받고 오름차순으로 정렬한 뒤, 이진 탐색을 이용하여 O(log n)에 결과값을 출력한다.

코드

#include <iostream>
#include <algorithm>
using namespace std;

int search(int key, int arrA[], int N) {	// 이진탐색
	int s = 0;
	int e = N - 1;

	while (e - s >= 0) {
		int m = (s + e) / 2;

		if (key == arrA[m]) {
			return 1;
		}
		else if (key > arrA[m]) {
			s = m + 1;
		}
		else {
			e = m - 1;
		}
	}
	return 0;
}
int main() {
	int N;
	cin >> N;
	int* arrA = new int[N];
	for (int i = 0; i < N; i++) {
		cin >> arrA[i];
	}
	int M;
	cin >> M;
	int* arrB = new int[M];
	for (int i = 0; i < M; i++) {
		cin >> arrB[i];
	}
	sort(arrA, arrA + N);	// 오름차순 정렬

	for (int i = 0; i < M; i++) {
		cout << search(arrB[i], arrA, N) << "\n";
	}
	return 0;
}

시행착오

1. 당연히 이중 for문을 사용할 생각이었는데, 시간 초과가 떴다. for문을 불필요하게 돌기보다는 이진 탐색을 이용하는 것이 더욱 효율적일 것이다.
2. 배열의 동적 할당을 생각하지 못하고 메모리를 많이 사용했다.
3. sort함수를 사용하지 않으면 수행 시간이 비교적 길다.
4. 함수를 main 바깥에 적는 연습이 필요하다. - 필요한 매개변수를 찾는 게 어려움