[백준 10816번] 숫자 카드 2

<문제 소개>

---

<소스 코드> - unordered_map

#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <unordered_map>
#include <cmath>
#include <stack>
#include <queue>
#include <algorithm>
#include <cstdlib>
using namespace std;

int main()
{
	// 쓰레드 환경이 아닐때 버퍼를 분리하여 처리속도를 빠르게 해줌
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;

	unordered_map<int, int> SG; // 상근이의 카드더미	

	for (int i = 0; i < N; i++)
	{
		int card;
		cin >> card;

		SG[card]++; // 카드 별로 갯수를 셈
	}

	int M;
	cin >> M;

	vector<int> Quest(M);

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

	for (int i = 0; i < Quest.size(); i++)
	{
		cout << SG[Quest[i]] << " ";
	}

	return 0;
}

 

<소스코드> - 이분탐색

#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <unordered_map>
#include <cmath>
#include <stack>
#include <queue>
#include <algorithm>
#include <cstdlib>
using namespace std;

int main()
{
	// 쓰레드 환경이 아닐때 버퍼를 분리하여 처리속도를 빠르게 해줌
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;

	vector<int> SG(N); // 상근이의 카드더미	

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

	sort(SG.begin(), SG.end()); // 이분탐색을 위해 정렬

	int M;
	cin >> M;

	vector<int> CardCount(M); // 카드번호별 개수를 담음

	for (int i = 0; i < M; i++)
	{
		int cardNum;
		cin >> cardNum;

		auto lower = lower_bound(SG.begin(), SG.end(), cardNum);
		auto upper = upper_bound(SG.begin(), SG.end(), cardNum);

		// 카드별 갯수 파악
		CardCount[i] = upper - lower;
	}

	for (int i = 0; i < CardCount.size(); i++)
	{
		cout << CardCount[i] << " ";
	}

	return 0;
}

---

<풀이과정> - unordered_map

1. N을 입력받고 상근이의 카드더미를 나타내는 key와 value 모두 int형으로 된 unordered_map, SG를 선언한다.

2. N만큼 반복하며 카드번호를 입력 받으면서 SG에 해당 카드번호를 key로 갖는 value값을 증가시켜준다.

3. M을 입력받고, 갯수를 구해야하는 카드번호를 담을 int형 벡터 Quest를 M의 크기로 선언한다.

4. M만큼 반복하며 주어진 입력을 Quest에 하나씩 담는다.

5. 담은 Quest의 원소들을 돌면서 SG에 key값으로 원소를 받아서 value 값을 하나씩 출력한다.

 

<풀이과정> - 이분 탐색

1. N을 입력받고 상근이의 카드를 나타낼 벡터 SG를 N의 크기로 선언한 뒤 N만큼 반복하며 입력을 받아 SG에 넣는다.

2. 이분탐색을 위해 내장함수 sort를 이용해 SG를 정렬한다.

3. M을 입력받고 카드번호별 개수를 담을 벡터 CardCount를 M의 크기로 선언한다.

4. M만큼 반복하며 카드번호를 입력받고, 내장함수 lower_bound와 upper_bound를 구하고, 두 수의 차가 현재 카드의 갯수를 의미하므로 CardCount에 해당 갯수 upper - lower를 넣어준다.

5. 반복이 끝난뒤 CardCount의 원소들을 하나씩 출력한다.

---

<코멘트>

처음에 그냥 map으로 했다가 시간초과가 나서 왜 그러지? 생각해보다가 정렬때문인가해서 unordered_map으로 바꿨더니 통과했다!(unorderd_map을 해시맵이라 하나보다)

다른 방법은 없는지 알아보다가 이분탐색을 사용하면 더 빠르다고 하길래 다시 풀어보았다.

upper_bound, lower_bound 함수가 내장되어 있는지 모르고 혼자 구현해서 풀었는데 시간초과나서 찾아보다가 알게되었다.ㅋㅋㅋ

---

<제출결과>

1. 이분탐색

2. 혼자 푼 이분탐색 - 시간초과

3. unordered_map

4. map