[baekjoon 10816] 숫자 카드2 - Hashmap, 이분탐색 (C++)

www.acmicpc.net/problem/10816

10816번: 숫자 카드 2

입력 수들을 받고, 찾고자 하는 수에 해당하는 수가 몇 개가 있는지 출력하는 문제다.

입력 개수는 50만 개, 찾는 수 또한 50만 개로 일반적인 배열에 넣고 선형 탐색을 하게 되면 O(N^2)로 시간제한 1초를 넘기게 된다.

보통 c++기준 N = 1억이면 1초라고 한다.

 

따라서 보통의 시간 복잡도가 O(1)인 HashMap을 이용하거나 O(logN)인 이분 탐색을 이용해야 한다.

(이분 탐색은 문제 풀고 나서 알았다.)

 

 - HashMap을 이용한 풀이

(통과한 코드인데 ios::sync_with_stdio(false)와 cin.tie(0)을 해주기 전에는 시간 초과가 나왔다.)

#include <iostream>
#include <unordered_map>

using namespace std;

unordered_map <int, int> m;
int N, M, card;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> card;
		m[card]++;
	}
	cin >> M;
	for (int i = 0; i < M; i++) {
		cin >> card;
		cout << m[card] << " ";
	}
}

 

이분 탐색을 이용한 풀이는 Algorithm STL의 upper_bound, lower_bound을 사용한 풀이가 있었다.

이분 탐색을 위해서 오름차순 정렬을 해주고, upper_bound와 lower_bound을 이용해서 결과를 출력했다.

 - upper_bound : 찾고자 하는 값의 다음 값이 최초로 나타나는 위치

 - lower_bound : 찾고자 하는 값 이상이 처음 나타나는 위치

 

즉, 1 2 4 4 6 7에서

lower_bound(~,~,4)의 결과 : 3 (4 이상의 값이 처음 나타나는 위치)

upper_bound(~,~,4)의 결과 : 5 (4를 초과하는 값이 처음 나타나는 위치)를 이용해서 

사이의 값을 빼주면 2가 나오고 이것은 결국 저장된 4의 개수가 된다.

#include <iostream>
#include <algorithm>

using namespace std;

int arr[500002];
int N, M, card;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> card;
		arr[i] = card;
	}
	sort(arr, arr + N); // 이분탐색을 위해 오름차순 정렬

	cin >> M;
	for (int i = 0; i < M; i++) {
		cin >> card;
		cout << upper_bound(arr, arr + N, card) - lower_bound(arr, arr + N, card)<<" ";
	}
}

 

 

위가 이분탐색, 아래가 HashMap을 이용한 메모리, 시간이다.

 

그럼 왜 시간 복잡도가 더 작은 HashMap이 더 오래 걸렸을까?

 

질문하기에서 어떤 분께서 잘 설명을 해주셔서 가져와보았다.

-------------------------------------------------------------------

현실 세계에서는 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)같이 시간 복잡도가 크게 차이나는 경우에도 자주 일어납니다.

출처 : www.acmicpc.net/board/view/57406

-------------------------------------------------------------------

 

그렇다고 한다. O(logN)이 O(1) 보다 더 빠를 수 있다는 사실을 알게 되었다.