[알고리즘] C++ 백준 1920 수 찾기

백준 1920

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

1920번: 수 찾기

풀이 전 나의 생각

전형적인 이분탐색 문제다.

 

첫 번째로 주어지는 정수N의 배열은 10만 까지 주어진다.

두 번째로 주어지는 정수M의 배열도 10만 까지 주어진다.

 

이분탐색을 몰랐다면 가장 처음으로 생각해낼 수 있는 풀이방법은 

이중 for문을 이용하여 정수M을 정수N 배열에서 찾아낼 것이다.

이런 풀이로 진행한다면 백준 문제에서 나온 테스트 케이스는 풀릴 것이다.

하지만 시간복잡도가 O(n)^2 이기 때문에 10만 * 10만 = 10,000,000,000번 (100억) 계산이 진행될 것이다.

 

시간복잡도를 잘 몰라도 100억번을 계산한다고 하면 시간제한 1초를 만족시킬 수 없다는 것은 어느정도 느낄 것이다.

그렇기 때문에 다른 방법으로 문제를 풀어야한다.

 

따라서 이를 가능하게 해줄 수 있는 방법이 이분탐색이다.

이분탐색의 기본적인 진행과정은 다음과 같다.

 

여기서 시작과 끝은 배열의 순번을 말하며 현재 배열은 

0부터 시작한다

 

1. 탐색할 배열을 오름차순으로 정렬해준다.

4 1 5 2 3 -> 1 2 3 4 5

 

2. 시작과 끝을 더하여 2로 나눈 값을 중간값으로 설정한다.

mid = (0 + 4) / 2 = 2 

 

3. 정수X가 탐색 배열의 중간값과 같다면 탐색에 성공한 것이니 1을 출력하고 종료한다.

if (arr[mid] == num[i]) cout << "1"

 

4. 정수X가 현재 탐색 배열의 중간값 보다 크다면 현재 중간값은 탐색이 완료되서 탐색 할 필요가

없기 때문에 중간값 + 1한 위치를 시작점으로 두고 2번으로 돌아가 재탐색 한다.

(start)1, 2, (mid)3, 4, (end)5  -> 1, 2, 3, (start)4, (end)5

 

5. 정수X가 현재 탐색 배열의 중간값 보다 작다면 현재 중간값은 탐색이 완료되서 탐색 할 필요가

없기 때문에 중간값 - 1한 위치를 끝점으로 두고 2번으로 돌아가 재탐색 한다.

(start)1, 2, (mid)3, 4, (end)5  -> (start)1, (end) 2, 3, 4, 5

 

6. 시작점보다 끝점이 더 크다면 더 이상 탐색이 불가능 하다는 것을 의미하니 반복문을 종료해준다.

1, (end)2, (start)3, 4, 5 -> start와 end사이의 값 존재하지 않음

 

이것이 이분탐색의 기본적인 탐색 과정이며

O(logN)의 시간복잡도를 가지고 있기 때문에 시간제한을 지키면서 문제를 풀어낼 수 있다.

 

O(logN)인 이유는 한 번 탐색을 진행할 때 마다 시작과 끝을 반으로 나누기 때문에

그만큼 탐색횟수가 줄어들기 때문이다.

 

 

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
#include <cstdio>

using namespace std;

int arr[100001];
int num[100001];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int n, m;

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> arr[i];
	}

	sort(arr, arr + n);

	cin >> m;

	for (int i = 0; i < m; i++)
	{
		cin >> num[i];
	}
	
	for (int i = 0; i < m; i++)
	{
		int start = 0;
		int end = n - 1;

		while (true)
		{
			if (start > end)
			{
				cout << "0" << '\n';
				break;
			}

			int mid = (start + end) / 2;

			if (arr[mid] == num[i])
			{
				cout << "1" << '\n';
				break;
			}		
			else if (num[i] > arr[mid])
			{
				start = mid + 1;
			}
			else
			{
				end = mid - 1;
			}			
		}
	}
}