백준) 10816번: 숫자 카드 2 in C/C++ (이진 트리, map)

Problem

10816번: 숫자 카드 2

Solution

 

이전에 풀었던 1920번 : 수 찾기 문제와 흡사하다.

다만 이번 문제에서는 주어진 N개의 정수에서 어떤 숫자가 존재하는 탐색하는 것이 아니라, 그 숫자가 총 몇 개 있는지를 구해야 한다.

 

문제 알고리즘 분류로는 '이분 탐색'과 '해시를 사용한 집합과 맵'이다.

즉 이진 탐색을 통해서 문제를 풀 수도 있으며,

해시를 사용한 집합 또는 맵 자료구조를 통해 풀 수도 있다.

 

1. 이진 탐색

이미 정렬된 수열에 대해서 탐색한다는 것을 이용해

탐색하는 값이 가장 처음 나타나는 위치인 Lower Bound,

그리고 탐색하는 값보다 큰 값이 가장 처음 나타나는 위치인 Upper Bound를 구하고

Upper Bound - Lower Bound 값을 구해 탐색하는 값이 총 몇 개 있는지를 구할 수 있다는 것이다.

 

예를 들어 이미 오름차순으로 정렬된 1, 1, 2, 2, 2, 3, 3, 4, 4 가 있을 때,

Lower Bound는 index가 2이고, Upper Bound는 index가 5이므로

5 - 2 = 3, 즉 2가 3개 있는 것을 구할 수 있다.

 

C++에서는 이진 탐색에서의 Lower Bound, Upper Bound를 찾을 수 있는 함수 라이브러리를 제공한다.

다만 각 함수의 반환값은 인덱스가 아니라 그 위치의 주소값이므로 인덱스를 구하기 위해서는 배열의 처음 주소를 빼야 한다.

 

(예시 코드)

#include <stdio.h>
#include <algorithm>

using namespace std;

int main(){
	int arr[10] = {1, 1, 2, 2, 2, 3, 3, 4, 5, 6};
	
	int lb_index = lower_bound(arr, arr+10, 2) - arr; // 2에 대한 lower_bound의 위치 인덱스. 출력값 2.
	int ub_index = upper_bound(arr, arr+10, 2) - arr; // 2에 대한 upper_bound의 위치 인덱스. 출력값 5.
	
	printf("%d\n", lb_index);
	printf("%d\n", ub_index);
	printf("%d", ub_index-lb_index); // arr 배열 내 2의 총 개수. 출력값 3.
	
	return 0;
}

 

2. Map

map은 각 내부 노드가 유일한 Key와 하나의 Value 한 쌍으로 이루어진 트리 구조이다.

C++에서 일반 map과 unordered map 가 있는데, (key가 유일하지 않은 multimap 제외)

map은 내부 노드들이 key를 기준으로 오름차순 정렬되는 구조이고,

unordered map은 정렬을 하지 않는다고 한다.

 

map은 노드의 삽입, 접근, 삭제가 O(logN),

unordered map은 평균 상수 시간 O(1) 이 걸린다.

 

따라서 어떤 노드를 추가할 때마다 드는 오버헤드는 당연히 map이 더 크기 때문에 이번 문제처럼 정렬이 필요하지 않고, 노드 개수가 매우 크다면 unordered_map을 쓰면 된다.

 

이 문제에서 unordered_map 를 사용하기 위해,

key는 숫자 카드에 적혀있는 정수를, 그리고 value는 key 정수가 적혀있는 숫자 카드의 개수를 저장하도록 한다.

 

참고로 C++의 경우 unordered_map에 key를 넣으면 value는 자동으로 0을 갖는다고 한다.

 

Code

1. 이진 탐색의 upper, lower bound 이용.

#include <stdio.h>
#include <algorithm>

using namespace std;

int arr[500000];

int main(){
	int N, M, i, temp;
	
	scanf("%d", &N);
	for(i=0;i<N;i++)
		scanf("%d", &arr[i]);
	
	sort(arr, arr+N);
	
	scanf("%d", &M);
	for(i=0;i<M;i++){
		scanf("%d", &temp);
		int lb = lower_bound(arr, arr+N, temp) - arr;
		int ub = upper_bound(arr, arr+N, temp) - arr;
		printf("%d ", ub - lb);
	}
	
	return 0;
}

 

2. unordered_map 이용.

#include <stdio.h>
#include <unordered_map>

using namespace std;

int main(){
	int N, M, i, temp;
	unordered_map<int, int>m;
	
	scanf("%d", &N);
	for(i=0;i<N;i++){
		scanf("%d", &temp);
		m[temp] += 1; // key가 temp인 노드를 접근시 value에 1 씩 더해준다.
	}
	
	scanf("%d", &M);
	
	for(i=0;i<M;i++){
		scanf("%d", &temp);
		printf("%d ", m[temp]);
	}
	
	return 0;
}