[Baekjoon] 1920번: 수 찾기

 

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

1920번: 수 찾기

 

---

 

문제 해결 과정

착안

반복적으로 탐색을 빠르게 수행하는 것이 문제에서 요구하는 핵심이므로, 아래와 같이 일반적으로 탐색 속도가 매우 빠른 것으로 알려져 있는 방법으로 각각 문제를 해결하고자 하였다.

 

• 해시(hash) 맵을 사용한 방법
• 이진 탐색(binary search, 이분 탐색)을 사용하는 방법 

 

구현

[스포 주의] (해시 맵 사용) 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

// 해시 맵 사용

#include <iostream>
#include <unordered_set>

using namespace std;

unordered_set<int> Numbers;

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

	int N;
	cin >> N;
	while (N--)
	{
		int num;
		cin >> num;
		Numbers.emplace(num);
	}

	cin >> N;
	while(N--)
	{
		int num;
		cin >> num;
		auto iter = Numbers.find(num);
		cout << (iter != Numbers.end() ? "1" : "0") << "\n";
	}

	return 0;
}

 

 

[스포 주의] (이진 탐색 사용) 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

// 이진 탐색 사용

#include <iostream>
#include <algorithm>

using namespace std;

int Numbers[100000];

void BinarySearch(int num, int left, int right)
{
	while (left <= right)
	{
		int middle = (left + right) / 2;
		if (num == Numbers[middle])
		{
			cout << "1\n";
			return;
		}

		if (num < Numbers[middle])
			right = middle - 1;
		else
			left = middle + 1;
	}

	cout << "0\n";
}

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

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

	sort(&Numbers[0], &Numbers[N]);

	int M;
	cin >> M;
	while (M--)
	{
		int num;
		cin >> num;
		BinarySearch(num, 0, N - 1);
	}

	return 0;
}

 

 

실행 결과

위: 이진 탐색을 사용해 문제를 해결한 결과, 아래: 해시 맵을 사용해 문제를 해결한 결과

 

해시 맵의 경우에는 문자열 데이터를 다룰 때에 더 효과적인 것 같다.