[C++] 백준 10816 숫자 카드2

 

백준10816

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

10816번: 숫자 카드 2

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

 

 

풀기 전 생각

처음 문제를 풀었을 때는 당연히 맵을 사용하면 가장 빠르게 해결될 줄 알았다.

이유는 해쉬를 사용한 탐색이기 때문에 O(1)의 성능을 가지고 있기 때문이었다.

 

풀이1

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

using namespace std;

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

	int n = 0;
	int m = 0;
	int nVal = 0;
	
	cin >> n;

	map<int, int> map;	

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

	cin >> m;

	for (int i = 0; i < m; i++)
	{
		cin >> nVal;
		cout << map[nVal] << " ";
	}		
}

 

 

하지만 풀고나서 실행시간을 보니 

 

뭔가 잘못됨을 느꼈다.. 

 

심지어 

ios::sync_with_stdio(false);
cin.tie(0);

이 코드 단락을 쓰지 않으면 통과 되지도 않는다.

 

그래서 찾아보니 

"N에 관계없이 항상 50번의 비교로 수를 찾는 어떤 O(1) 알고리즘과 N에 대해 ceil(lgN)번의 비교를 하는 O(lgN) 알고리즘이 있으면,

복잡도만 봤을 때는 O(1)이 나음에도 불구하고, N이 조 단위를 넘어가지 않는 이상 O(lgN)이 O(1)보다도 빠릅니다."

 

라는 글이 있었다. 

 

어떤 자료구조에서 최악, 최고를 빅오표기법으로 나타낸적은 있어도 빅오 표기법의 최악, 최고가 포함되 있을 줄은

상상도 못했다.

 

그렇기 때문에 O(logN)의 성능을 가지는 이분탐색으로 다시 풀어 볼 필요가 있었다.

 

풀이2

#include <iostream>
#include <algorithm>

using namespace std;

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

	int n = 0;
	int m = 0;
	int nVal = 0;
	
	int arr[500002];
	
	cin >> n;

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

	sort(arr, arr + n);

	cin >> m;

	for (int i = 0; i < m; i++)
	{
		cin >> nVal;
		cout << upper_bound(arr, arr + n, nVal) - lower_bound(arr, arr + n, nVal) << " ";
	}		
}

 

여기서 vector나 map을 사용하는 것이 아닌 배열을 사용했는데 고정된 크기에서는 배열이 속도가 가장 빠르기 때문이다.

이분탐색은 upper_bound, lower_bound를 사용한 부분을 보면되는데

 

값이 1, 3, 3, 4 가 있다고 가정하고 3을 기준으로 이분탐색을 진행한다면

lower_bound는 3이 처음으로 나온 위치 = 2를 반환하고

upper_bound는 3이 더 이상 나오지 않는 위치 = 4를 반환한다.

 

그래서 upper_bound - lower_bound를 하게되면 기준으로 잡은 숫자의 개수가 나오게 된다.

 

 

시간을 300ms나 줄인 것을 확인할 수 있다.