[BOJ 10816] 숫자 카드2

 

10816번: 숫자 카드 2

C++ STL이 새삼 정말 간편하다고 느낀 문제입니다..

이분 탐색을 위해 '정렬'을 한 후 중복까지 해결할 방법을 고민하는 과정에서 시간이 꽤 많이 걸렸습니다.

 

일단 카드의 개수가 500,000개이기 때문에 O(N^2) 이용하면 100% 시간초과입니다.

카드를 '찾는' 것이기 때문에 이분탐색을 바로 떠올릴 수 있지만, 그 카드가 '몇 장 있는지'까지 찾아야 하기 때문에

단순히 찾는 것 이상으로 더 고민해봐야 합니다.

10
6 3 2 10 10 10 -10 -10 7 3
8
10 9 -5 2 3 4 5 -10

이분 탐색을 사용하기 위해

  1) 처음 입력받는 카드를 정렬을 합니다.

     6 3 2 10 10 10 -10 -10 7 3

→ -10 -10 2 3 3 6 7 10 10 10

 

우리가 궁금한 것은 찾은 카드가 '몇 장'인지입니다. 근데, 어떤 카드가 '몇 장'인지를 미리 기록 해둔다면?

그러면 카드를 찾았을 때 그 카드가 몇 장인지를 기록해두었기 때문에 바로 return해주면 되겠습니다.

 

위에 정렬되있는 숫자들이 중복을 제외하면 -10,2,3,6,7,10 입니다.

이들을 pair<값, 몇 장>의 개념으로 저장하고 pair.first(값) == 찾고자 하는 값이라면

pair.second(몇 장)를 return하는 방식으로 풀이하면 되겠습니다.

pair에 값을 저장해줄 때는 어차피 v가 정렬이 되있기 때문에 

pair에 가장 작은 값부터 순서대로 들어갈 것이고, 같으면 pair.second++,

pair가 가지고 있는 값이 v와 다르다는 것은 더 이상 같은 카드가 없다는 의미로 삽입(push_back)해줍니다.

이후 이분탐색을 이용하여 답 출력!

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

using namespace std;

vector <pair<int, int>> compare;

void recursive(int left, int right, int target)
{
	int ans = 0;
	while (left <= right)
	{
		int mid = (left + right) / 2;
		if (target == compare[mid].first)
		{
			ans = compare[mid].second;
			break;
		}

		else if (target < compare[mid].first)
		{
			right = mid - 1;
		}
		else if (target > compare[mid].first)
		{
			left = mid + 1;
		}
	}

	printf("%d ", ans);
}
int main(void)
{
	vector<int> v;
	vector<int>v1;
	int n;

	scanf("%d", &n);

	int num;
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &num);
		v.push_back(num);
	}


	sort(v.begin(), v.end());

	compare.push_back({v[0], 1});

	int idx = 0;
	for (int i = 1; i < n; i++)
	{
		if (v[i] == compare[idx].first)
			compare[idx].second++;

		else {
			compare.push_back({ v[i],1 });
			idx++;
		}
	}

	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &num);
		v1.push_back(num);
	}
	for (int i = 0; i < n; i++)
	{
		recursive(0, compare.size()-1, v1[i]);
	}
}

 

근데, C++ STL에서 upper_bound와 lower_bound함수를 이용하면 매우 문제가 간편해집니다..

 

upper_bound는 내가 찾고자 하는 값보다 '큰 값'이 처음으로 출현한 위치를 반환.

lower_bound는 내가 찾고자 하는 값보다 '크거나 같은' 값이 처음 출현한 위치를 반환.

 

-10 -10 2 3 3 6 7 10 10 10에서

 

-10이 처음 출현한 위치는 0, (lower_bound)

-10보다 큰 값이 처음 출현한 위치는 2(upper_bound)

즉, 이 두 개를 빼주어 2개라는 것을 안다는 것입니다.

 

3이 처음 출현한 위치는 3, 

3보다 큰 값이 처음 출현한 위치는 5.

이 두개를 빼면 2개.

 

이 upper_bound와 lower_bound 함수 자체가 이미 O(logN)의 시간복잡도로 구현이 되어있기 때문에,

그냥 사용하면 됩니다... 문제해결방법을 더 많이 알면 이런 것을 바로바로 떠올릴 수 있겠죠..? 

STL의 편리성을 적극 이용합시다..!!

 

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

using namespace std;

int main(void)
{

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	vector<int> a;
	vector<int> b;

	int n;
	cin >> n;
	a.resize(n);
	for (int i = 0; i < n; i++)
		cin >> a[i];

	cin >> n;
	b.resize(n);

	for (int i = 0; i < n; i++)
		cin >> b[i];

	sort(a.begin(), a.end());

	for (int i = 0; i < n; i++)
	{
		cout << upper_bound(a.begin(),a.end(), b[i]) - lower_bound(a.begin(),a.end(), b[i]) << " ";
	}
}