< 백준 BaekJoon : 10816번 숫자 카드2> C++

<<문제>>

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

10816번: 숫자 카드 2

 

숫자카드 문제 2번입니다.

이전에 풀었던 숫자 카드 문제가 있었죠?

 

< 백준 BaekJoon : 10815번 숫자 카드 > C++

달라진 점은 1번 문제가 보유 여부를 묻는 문제였다면, 2번 문제는 보유 개수를 묻는 문제입니다.

 

<<풀이>>

1번 문제를 풀었을 때와 크게 다르지 않습니다. 0-20,000,000 배열에 0,1 대신 개수를 저장해주면 됩니다.

 

<<코드>>

#include <iostream>
using namespace std;

/*
BaekJoon_10816 : 숫자 카드 2
	상근 - 숫자 카드 n개 보유
	정수 M개가 주어졌을때, M개의 카드를 상근이가 각각 몇개를 보유하고 있는지 구하는 문제
	1<= n, m <=500,000
	카드에 적힌 수 -10,000,000 ~ 10,000,000 
*/

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int numN;
	int numM;
	int* arrN = new int [20000001](); // -10,000,000 ~ 10,000,000을 0 ~ 20,000,000 으로 생각
	
	
	cin >> numN;
	int input;
	for (int i = 0; i < numN; i++) {
		cin >> input;
		arrN[input + 10000000]++;
	}

	cin >> numM;
	for (int i = 0; i < numM; i++) {
		cin >> input;
		cout << arrN[input + 10000000] << " ";
	}

	delete[] arrN;
	return 0;
}

 

그리고 글 쓰던 중 생각해보았는데... 

map을 사용하면 더 쉽게 풀 수 있을 것 같았습니다.

 

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

/*
BaekJoon_10816 : 숫자 카드 2
	상근 - 숫자 카드 n개 보유
	정수 M개가 주어졌을때, M개의 카드를 상근이가 각각 몇개를 보유하고 있는지 구하는 문제
	1<= n, m <=500,000
	카드에 적힌 수 -10,000,000 ~ 10,000,000 
*/

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int numN;
	int numM;
	map<int, int> mapN;
	
	
	cin >> numN;
	int input;
	for (int i = 0; i < numN; i++) {
		cin >> input;
		mapN[input]++;
	}

	cin >> numM;
	for (int i = 0; i < numM; i++) {
		cin >> input;
		cout << mapN[input] << " ";
	}
	return 0;
}

더 직관적인것 같네요

 

아래가 1번 풀이 위가 2번 풀이

map을 사용한 풀이가 시간이 3배 정도 더 걸리지만 메모리 사용량이 반절에 가깝네요.

20,000,000개를 모두 할당한 배열이 아무래도 메모리 사용량이 더 많이 나오는 것 같습니다.

 

<<깃헙>>

1번 풀이

GitHub - J2on/BaekjoonOnlineJudge: My Study

2번 풀이

GitHub - J2on/BaekjoonOnlineJudge: My Study