[백준] 10816번 : 숫자 카드 2 | binary search & unordered map (C++)

---

문제

---

풀이

1. binary_search를 이용해 풀이했다. O(logn)
2. 문제를 맞춘 후, unordered_map을 이용해도 가능한 것을 확인해 사용해보았다. O(1)

 

이 문제를 풀며 놀라웠던 점은 시간복잡도가 O(logn)인 binary_search가 O(1)인 unordered_map보다 빨랐다는 것이다.

 

찾아보니 이에 대한 질문 글이 있어 답변을 가져왔다.

 현실 세계에서는 N이 무한히 큰 경우가 거의 없기 때문에 O(lgN)과 O(1) 정도의 차이는 N의 크기에 따라 시간복잡도에 붙은 상수로 자주 뒤집어집니다.

 가령, 최소한의 비교로 원하는 수를 찾아야 하는 가상의 문제가 있다고 합시다.

 N에 관계없이 항상 50번의 비교로 수를 찾는 어떤 O(1) 알고리즘과 N에 대해 ceil(lgN)번의 비교를 하는 O(lgN) 알고리즘이 있으면, 복잡도만 봤을 때는 O(1)이 나음에도 불구하고, N이 조 단위를 넘어가지 않는 이상 O(lgN)이 O(1)보다도 빠릅니다.

 이런 상황은 심지어 O(N)과 O(N^2)같이 시간복잡도가 크게 차이나는 경우에도 자주 일어납니다.

 

 

글 읽기 - HashMap이 이분탐색보다 느린 이유가 뭔가요?

---

 첫 번째 코드 | binary_search, O(logn)

• lower_bound: 찾고자하는 값 (이상)이 처음 나타나는 위치
• upper_bound: 찾고자 하는 값의 다음 값이 나타나는 최초의 위치
• ex) 1 3 5 5 7 9 이고 findnum = 4라면, lower_bound = 3, upper_bound = 5
• 따라서, 차를 통해 개수를 구할 수 있음.

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

//	binary search 풀이 | O(logn)
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n, m, listnum, findnum;
	vector<int> listv;

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> listnum;
		listv.push_back(listnum);
	}

	sort(listv.begin(), listv.end());

	cin >> m;

	for (int i = 0; i < m; i++) {
		cin >> findnum;

		// lower_bound: 찾고자하는 값 (이상)이 처음 나타나는 위치
		// upper_bound: 찾고자 하는 값의 다음 값이 나타나는 최초의 위치
		// ex) 1 3 5 5 7 9 이고 findnum = 4라면
		// lower_bound = 3, upper_bound = 5 | 따라서, 차를 통해 개수를 구할 수 있음.
		cout << upper_bound(listv.begin(), listv.end(), findnum) - lower_bound(listv.begin(), listv.end(), findnum) << " ";

	}
    
	return 0;
}

 

 

---

 두 번째 코드 | unordered_map, O(1)

• map: red-black tree, O(logn) | unordered_map: hash table, O(1) | vector: O(n)
• unordered_map은 많은 양의 데이터를 저장할 때 good (수천 이상)
• 따라서, 저장한 자료가 적다면 메모리 낭비와 검색 시 오버헤드 발생
• 정렬 없이 자료를 보관하므로, map 보다 속도가 빠름. 

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

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	// map: red-black tree, O(logn) | unordered_map: hash table, O(1) | vector: O(n)
	// unordered_map은 많은 양의 데이터를 저장할 때 good (수천 이상)
    // 따라서, 저장한 자료가 적다면 메모리 낭비와 검색 시 오버헤드 발생
	unordered_map <int, int> um;		// 정렬 없이 자료를 보관하므로, map 보다 속도가 빠름. 
	int n, m, listnum, findnum;

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> listnum;
		um[listnum]++;		// listnum의 개수에 따라 unordered_map에 저장
	}

	cin >> m;

	for (int i = 0; i < m; i++) {
		cin >> findnum;
		// unordered_map에 <key, value> 형태로 저장, value가 true로 존재하면 같은 문자열 O
		cout << um[findnum] << " ";
	}

	return 0;
}

---

결과

 

10816번: 숫자 카드 2