1-1. 탐색과 정렬 (1)_#1920 수 찾기 [C/C++]

문제

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안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -2^31 보다 크거나 같고 2^31보다 작다.

 

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

 

정리

- 크기가 안정해진 배열 입력

- 이진 탐색 (Binary Search)

- cin 속도 향상

 

처음 백준에 알짱대기 시작했을때 크기가 안정해진 배열을 어떻게 입력받을까 하다가

int* a = new int[n]; 이렇게 동적 할당을 받는 방법을 사용하였다.

본 문제를 공부하며 보통 프로그래밍 문제를 풀 때에는 동적 할당을 하는 방식이 아닌 나올 수 있는 최대 크기의 배열 크기로 정적 할당하여 사용하는 것이 일반적이라는 것을 알았다.

(+vector을 사용하는 방법)

 

이진탐색을 사용하기 위해 sort 함수를 사용한다.

sort(배열의 포인터, 배열의 포인터 + 크기)
- C++ algorithm STL에서 제공하는 함수
- 시간 복잡도 : nlogn (최악에도 nlogn)
- 퀵정렬을 기반으로 힙정렬과 삽입정렬을 섞은 방식
- 두번째 인자는 종료 인덱스가 아니라 배열의 크기를 더해야 한다 (∵ begin <=arr <end)

 

이진 탐색
- 정렬된 데이터에서 중간값과 찾는 데이터를 비교해나감
- 시간 복잡도 : O(logn)
- 연결리스트 데이터에서는 이진탐색 불가능

binary_search(시작점, 끝점, 찾는 값)
- C++ algorithm STL에서 제공하는 함수

 

이 문제에서 또 하나 주의할 점이 시간을 위해 endl 대신 "/n"을 이용해야 하는 것과 (endl은 출력 버퍼를 비워야 해서 훨씬 느림) cin의 속도 향상을 위해 ios_base::sync_with_stdio(0); cin.tie(0);을 추가해야 한다는 점이다.

 

C++에서도 성능면으로 printf()와 "/n"을 사용하는 것이 나을 때도 존재한다. cout, cin, endl은 사용성이 좋으나 성능 문제를 일으킬 수 있다.

 

 

코드

#include <iostream>
#include <algorithm>
using namespace std;
int a[100000];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
	int n, m, tmp;
	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 >> tmp;
		if (binary_search(a, a + n, tmp)) cout << "1\n";
		else cout << "0\n";
	}
}