백준 10815. 숫자 카드

숫자 카드

간단한 탐색 문제

1. 간단 설명

---

숫자카드 N개를 가지고 있다

정수 M개가 주어졌을 때 이 수가 적혀있는 숫자를 갖고 있는지 아닌지 구하는 프로그램

• N (1 ≤ N ≤ 500,000)
• 각 숫자는 -10,000,000 보다 크거나 같고, 10,000,000보다 작거나 같다
• M(1 ≤ M ≤ 500,000)
• 넷째 줄 부터 M개는 상근이가 갖고있는지 구해야할 M개의 정수

2. 알고리즘

---

50만개의 숫자가 주어지고, 그 중에서 일치하는 숫자가 있는지 찾는 문제

최악의 케이스인 경우

상근이가 가진 숫자 카드가 50만개, 확인해야하는 카드의 숫자 카드가 50만개인 경우

브루트 포스 방식으로 계산한다면 각 M개의 숫자에 대해 N개의 숫자를 선형 탐색을 수행해야 한다

이는 약 2500억으로 2초의 시간제한을 초과한다

탐색 방법 중 시간복잡도가 효율적인 이진 탐색을 사용한다면

상근이가 가진 숫자카드를 정렬하는데 시간 복잡도 O(NlogN)

각 M개의 숫자에 대해 이진 탐색을 수행하는 시간복잡도 O(MlogN)으로

총 시간 복잡도는 O(NlogN + MlogN)이다

이는 약 19,000,000 정도로 2초 내에 풀이 가능

또 다른 방법으로는 해시맵 방식을 사용하면

숫자 카드를 해시맵에 저장하는데 O(N)

M개의 숫자에 대해 해시맵에 존재 여부 체크 O(M)

총 시간 복잡도는 O(N+M)으로 100만이므로 가장 효율적으로 동작한다

3. 소스코드

---

• 이진 탐색을 이용한 방법

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

using namespace std;

int N, M;
vector<int> v1, v2;

void Input() {
	freopen_s(new FILE*, "input.txt", "r", stdin);
	cin >> N;
	for (int i = 0; i < N; i++) {
		int tmp; cin >> tmp;
		v1.push_back(tmp);
	}
	cin >> M;
	for (int i = 0; i < M; i++) {
		int tmp; cin >> tmp;
		v2.push_back(tmp);
	}
}

bool MyBinarySearch(int target) {
	int start = 0, end = v1.size() - 1;

	while (start <= end) {
		int mid = (start + end) / 2;
		// 원하는 값을 찾은 경우
		if (target == v1[mid]) return true;

		// 중간값보다 목표가 작은 경우, 앞쪽을 검사
		if (target < v1[mid])
			end = mid - 1;
		// 중간값 보다 목표가 큰 경우, 뒷쪽을 검사
		else if (target > v1[mid])
			start = mid + 1;
	}
	// 끝까지 탐색했지만 값이 없는 경우 
	return false; 
}

int main() {
	Input();

	sort(v1.begin(), v1.end());
	
	for (int e : v2) {
		if (MyBinarySearch(e)) cout << "1 ";
		else cout << "0 ";
	}

	return 0;
}

• 해시맵을 사용한 풀이 방법

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

int N, M;
unordered_set<int> cards;
vector<int> quaries;

void Input() {
	freopen_s(new FILE*, "input.txt", "r", stdin);
	cin >> N;
	for (int i = 0; i < N; i++) {
		int tmp; cin >> tmp;
		cards.insert(tmp);
	}
	cin >> M;
	for (int i = 0; i < M; i++) {
		int tmp; cin >> tmp;
		quaries.push_back(tmp);
	}
}

int main() {
	Input();

	for (int i = 0; i < M; i++) {
		if (cards.find(quaries[i]) != cards.end()) {
			cout << "1 ";
		}
		else {
			cout << "0 ";
		}
	}

	return 0;
}

아래가 이진 탐색을 이용한 방법, 위가 해시맵을 사용한 방법이다

이진 탐색을 이용하는 방법은 메모리 사용량이 상대적으로 적다

그러나 정렬된 상태에서만 사용 가능하므로, 사전에 정렬이 필요하다

시간복잡도가 O(MlogN)이므로 M과 N이 매우 클 때, 해시맵보다 느릴 수 있다

또한 범위 검색도 가능함

해시맵 풀이 과정은 평균적으로 O(1)의 조회 시간을 가지므로 매우 빠르게 탐색할 수 있다

그리고, 라이브러리를 사용해서 쉽게 구현할 수 있으므로 insert 함수와 find로 삽입, 탐색을 수행할 수 있다

메모리 사용량이 벡터보다 많고, 충돌이 발생한다면 시간 복잡도가 증가하게 된다

즉 정리하자면

이진 탐색은 데이터를 정렬된 상태로 유지하면서 작업을 수행해야할 때, 메모리가 제한적일때 사용하고

해시맵은 특정값의 존재 여부만 확인할 때, 속도가 제일 중요할 때 사용하면 좋다