[C++/BOJ] 10816 : 숫자카드2 - unordered_map, upperbound, lowerbound

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

---

⊙ 문제

주어진 N개의 수들에서 M개 수들의 개수를 출력하는 문제이다.

---

⊙ 문제 접근 과정

처음 시도에서

주어진 N개 수들을 하나의 배열에 넣고, 주어진 M개 수들을 하나의 배열에 넣어

lower_bound를 직접 함수로 구현하였는데, 잘못 구현하여 오류가 났다.

런타임 오류(segdefault), 시간초과, 틀림 오류가 났고,

 

두번째 시도로

인터넷에 찾아봐서

unordered_map 자료구조를 사용하여 O(1) 의 시간 안에 찾을 수 있게 구현했다.

 

세번째 시도로

upper_bound, lower_bound STL을 이용해 풀었다.

또한 추가로 두 함수를 직접 구현해봤다.

---

⊙ 문제 풀이

//첫번째 시도 - 틀린 부분이 있습니다.

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

int N, M;
int* nvec = NULL;
int* mvec = NULL;
string ans = "";
template<typename T>
T lower_bound(T& end, const T& key) {

	int l = 0, r = end;
	while (l < r) {
		int mid = (l + r) / 2;
		if (nvec[mid] < key) {
			l = mid + 1;

		}
		else if (nvec[mid] > key){
			r = mid - 1;
		}
		else {//같은 경우일때
			l = mid;
			while (nvec[l] == key) {
				l--;
			}
			break;
		}
	}
	if (nvec[l] != key && l == 0)
		return -1;
	return l;//값의 인덱스 반환
}


void input() {
	cin >> N;
	nvec = new int[N];
	for (int i = 0; i < N; i++)
		cin >> nvec[i];
	cin >> M;
	mvec = new int[M];
	for (int i = 0; i < M; i++)
		cin >> mvec[i];
	//nvec 배열 오름차순 나열
	sort(nvec, nvec + N);
}
void solve() {
	int order = 0;
	int low = 0, high = N - 1;
	int msave = M;
	while (1) {
		int search = mvec[order];
		//이분 탐색
		
		int k = lower_bound(high, search);
		if (k == -1)
			ans += "0 ";
		else
		{//최초로 search 값이 등장하는 nvec 배열에서의 인덱스 번호 찾음
			int count = 0;
			while (nvec[k] == search)
			{
				k++;
				count++;
			}
			
			ans += to_string(count);
			

		}
		if (order == msave - 1)
			break;
		ans += ' ';
		order++;
	}

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

	input();
	solve();
	cout << ans;
	return 0;
}

//두 번째 시도

: 카드에 적힌 수를 인덱스로 생각하여 unordered_map 의 key 값으로 사용한다.

#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] << " ";
	}
}

 

//세 번째 시도

#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) << " ";
	}
}

위의 upperbound와 lowerbound 함수를 직접 구현해보았다 (아래)

//upperbound

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

int main() {
	//정렬된 배열
	int arr[] = { 1, 2, 3, 3, 3, 4, 4, 5, 6, 7, 7, 7, 8, 8, 9 };
	int left = 0, right = sizeof(arr) / sizeof(int);

	int search;
	cin >> search;
	while (left < right) {
		int mid = (left + right) / 2;
		if (arr[mid] <= search)
			left = mid + 1;
		else if (arr[mid] > search)
			right = mid;


	}
	cout << "인덱스 " << right << "에 upperbound " << search << "값이 있습니다.";
	return 0;
}

//lowerbound

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

int main() {
	//정렬된 배열
	int arr[] = {1, 2, 3, 3, 3, 4, 4, 5, 6, 7, 7, 7, 8, 8, 9};
	int left = 0, right = sizeof(arr) / sizeof(int);
	
	int search;
	cin >> search;
	while (left < right) {
		int mid = (left + right) / 2;
		if (arr[mid] < search)
			left = mid + 1;
		else if (arr[mid] >= search)
			right = mid;
		
		
	}
	cout << "인덱스 "<< right << "에 lowerbound " << search << "값이 있습니다.";
	return 0;
}

위 함수들을 구현하기 위해 

아래 블로그를 참고하였다.

https://yoongrammer.tistory.com/105

Lower bound & Upper bound 개념 및 구현

---

⊙ 결과