[Baekjoon] 10816번: 숫자 카드 2

 

 

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

10816번: 숫자 카드 2

 

---

 

문제 해결 과정

착안

(최초 접근 방법) STL의 <unordered_map> 헤더에 포함된 std::unordered_map<> 클래스를 활용하여 입력되는 숫자를 키, 반복되는 개수를 값으로 가지도록 구현하고자 하였다(기본 오버로딩 되어있는 [] 연산자 활용).

 

(다른 접근 방법) 이전에 다른 문제들을 풀어보는 동안 숫자형 키 값을 사용할 때 std::unordered_map<> 클래스를 사용하는 것이 다소 비효율적인 결과를 보였었던 경험이 있었다. 따라서 해당 문제의 알고리즘 분류를 참고하여 아래와 같은 풀이 방법을 생각해보았다.

 

• 입력받는 카드의 번호를 전부 배열에 저장한다.
• 입력이 완료되면 해당 배열을 정렬한다.
• 이진 탐색(binary search, 이분 탐색)을 통해 찾고자 하는 카드가 처음 또는 마지막으로 등장하는 index를 구한다.
• 두 수의 차를 이용해 문제에서 요구하는 답을 구한다.

 

이진 탐색을 수행하는 함수의 구현을 응용하면 카드가 처음으로 등장하는 index와 마지막으로 등장하는 index + 1의 값을 구할 수 있으므로(아래 코드 참고), 이를 활용하여 문제를 해결하고자 하였다.

 

구현

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>
#include <algorithm>

using namespace std;

int N;
int Cards[500000];

int SearchLeft(int num)
{
	int left = 0, right = N;
	while (left < right)
	{
		int middle = (left + right) / 2;
		if (num > Cards[middle])
			left = middle + 1;
		else
			right = middle;
	}

	return right;
}

int SearchRight(int num)
{
	int left = 0, right = N;
	while (left < right)
	{
		int middle = (left + right) / 2;
		if (num < Cards[middle])
			right = middle;
		else
			left = middle + 1;
	}

	return left;
}

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

	cin >> N;

	for (int i = 0; i < N; i++)
		cin >> Cards[i];

	sort(&Cards[0], &Cards[N - 1] + 1);

	int M;
	cin >> M;
	while (M--)
	{
		int card;
		cin >> card;
		cout << SearchRight(card) - SearchLeft(card) << " ";
	}
	cout << "\n";

	return 0;
}

 

실행 결과