[BOJ 10816] 백준 숫자 카드 2 풀이 - C++

사용언어 :  C++

1. 이진탐색, 2. 맵

 

 

 

문제풀이

* binary search(이진탐색) 사용

숫자카드 값을 오름차순으로 정렬 후 해당 value값의 최소index,최대index를 구해 둘의 차이를 구한다.

 

1. 숫자 카드 값 배열에 대입하고 오름차순으로 정렬 

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

int start; int end; int center;
sort(arr, arr + N);

 

2. 최소 index, 최대 index 구하는 함수를 이용해 두 index의 차 구하기

int start; int end; int center;

sort(arr, arr + N); //오름차순으로 정렬
cin >> M;
for (int j = 0; j < M; j++) {
	cin >> tmp;
	int min = minIndex(arr, tmp, N); //최소 index 구하기
	int max = maxIndex(arr, tmp, N); //최대 index 구하기
	if (max == N - 1 && arr[N - 1] == tmp) 
		max++;
	cout << max - min << " ";
}

 

3. 최소index 구하는 함수

int minIndex(int*arr, int value,int size) {
	int start = 0;
	int end = size - 1;

	while (start < end) {
		int center = (start + end) / 2;
		if (value <= arr[center]) //해당 value가 비교하는 center보다 작거나 같으면 end에 center값 넣어주기
			end = center;
		else
			start = center + 1;
	}
	return end;
}

 

4. 최대index 구하는 함수

int maxIndex(int*arr, int value,int size) {
	int start = 0;
	int end = size - 1;

	while (start < end) {
		int center =(start+end)/ 2;
		if (value < arr[center]) { //해당 value가 비교하고자 하는 값보다 작으면 end값에 center넣어주기
			end = center;
		}
		else
			start =center + 1;
	}
	return end;
}

 

 

전체코드

(이진탐색 이용한 코드)

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

int arr[500000];
int N; int M; int tmp;
int rightIndex; int leftIndex;

 int minIndex(int*arr, int value,int size) {
	int start = 0;
	int end = size - 1;

	while (start < end) {
		int center = (start + end) / 2;
		if (value <= arr[center])
			end = center;
		else
			start = center + 1;
	}
	return end;
}

int maxIndex(int*arr, int value,int size) {
	int start = 0;
	int end = size - 1;

	while (start < end) {
		int center =(start+end)/ 2;
		if (value < arr[center]) {
			end = center;
		}
		else
			start =center + 1;
	}
	return end;
}

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

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

	int start; int end; int center;

	sort(arr, arr + N);
	cin >> M;
	for (int j = 0; j < M; j++) {
		cin >> tmp;
		int min = minIndex(arr, tmp, N);
		int max = maxIndex(arr, tmp, N);
		if (max == N - 1 && arr[N - 1] == tmp)
			max++;
		cout << max - min << " ";
	}
}

 

 

 

* map 이용해서 풀기 *

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

int N; int M;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int tmp;
	unordered_map<int, int> map;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> tmp; //입력받은 tmp값을 key로 갖는 map에 value값 1더해주기
		map[tmp]++;
	}
	cin >> M;
	for (int i = 0; i < M; i++) {
		cin >> tmp;
		cout << map[tmp]<<" ";
	}
}

---

총평

이진탐색 공부하려고 푼 문제지만, map을 이용해서 풀면 훨씬 쉬워진다! 아무대로 (key,value) 쌍으로 이루어져서 다루기 편리해지는 것 같다

---

문제 출처

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

10816번: 숫자 카드 2