[백준 10816번 C/C++] 숫자 카드 2

 

[백준 10816번 C/C++] 숫자 카드 2

 

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

 

10816번: 숫자 카드 2

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,0

www.acmicpc.net

 

---

 

해결전략

 

map과 set은 중복값을 허용하지 않는다.

따라서 이 문제에서는 unordered_map을 사용하였다. unordered_map에 사용되는 헤더는 #include <unordered_map>이다. 

 

 

주어진 카드 숫자를 인덱스 번호로 사용하는 unorder_map을 만든다.

 

unordered_map<int, int> unMap;

 

unMap[input]에서 input이 처음에 주어지는 카드 번호들이다. 위의 예제 입력의 경우 3, 10, -10은 중복으로 주어진다.

 

unMap[6]=1

unMap[3]=2

unMap[2]=1

unMap[10]=3

unMap[-10]=2

unMap[7]=1

 

unMap에 값을 넣으면 다음과 같을 것이다.

---

 

 

코드

 

unordered_map

#include <iostream>
#include <unordered_map>
using namespace std;
 
int n, m, input, card;
unordered_map<int, int> unMap;
 
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
 
	cin >> n;
	for(int i=0; i<n; i++){
		cin >> input;
		unMap[input]++;
	}
 
	cin >> m;
	for (int i = 0; i < m; i++) {
		cin >> card;
 
		cout << unMap[card]<< " ";
	}
 
	return 0;
}

 

 

map

#include <iostream>
#include <map>
using namespace std;
 
map<int, int> myMap;
 
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, m, input, card;
	
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> input;
		myMap[input]++;
	}
 
	cin >> m;
	for (int i = 0; i < m; i++) {
		cin >> card;
		cout << myMap[card] << " ";
	}
 
	return 0;
}

 

 

unordered_map이나 map 둘 다 사용가능하지만, 위의 경우 unordered_map이 더 빠르다.

 

---

 

 

 

map이나 unordered_map 이라는 자료형이 생각나지 않는 경우 

 

문제를 풀다보면 적절한 STL이 생각나지 않을 때도 있다.

이 문제의 경우 주어진 값의 범위가 "-10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다."라는 사실을 활용해서 배열을 만들 수 있다.

 

카드가 음수 일 수도 있기 때문에

Count[ input + 10000000 ] 로 만든다.

#include<iostream>
using namespace std;
 
int n, m, input, card;
int Count[20000001];
 
int main(void) {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	cout.tie(NULL);
		
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> input;
		Count[input + 10000000]++;
	}
	cin >> m;
	for (int i = 0; i < m; i++)
	{
		cin >> card;
		cout << Count[card + 10000000] << " ";
	}
}

 

 

 

 

 

---