BOJ 10816 - 숫자 카드 2

문제 링크

문제#

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

입력#

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

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

출력#

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

풀이#

이번에는 카드가 있는지 여부가 아니라 각 숫자의 등장 횟수를 물어본다. 같은 값을 여러 번 빠르게 답해야 하므로, 입력 카드를 한 번 읽으면서 값별 빈도를 미리 세어 두는 방식이 잘 맞는다.

현재 코드는 map<int, int>에 숫자별 개수를 누적한다. 이후 질의가 들어오면 해당 키가 있는지만 확인해서 저장된 빈도를 출력하고, 없는 값은 0을 출력한다. 문제에서 필요한 정보가 위치나 순서가 아니라 개수뿐이므로, 값별 카운트 테이블을 만드는 것으로 충분하다.

코드#

#include <iostream>
#include <map>
using namespace std;
 
int main() {
 
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
 
	int N;
	cin >> N;
	
	map<int, int> m;
	int num = 0;
 
	for (int i = 0; i < N; i++) {
		cin >> num;
 
		if (m.count(num))
			m[num]++;
		else
			m.insert(make_pair(num, 1));
	}
 
	int M;
	cin >> M;
 
	for (int j = 0; j < M; j++) {
		cin >> num;
		if (m.count(num))
			cout << m[num] << " ";
		else
			cout << "0" << " ";
	}
 
	return 0;
}

복잡도#

• 시간 복잡도: map 삽입과 조회가 각각 $O(\log N)$이므로 전체 시간 복잡도는 $O((N + M) \log N)$이다.
• 공간 복잡도: 서로 다른 카드 값의 빈도를 저장하므로 $O(N)$이다.

마무리#

숫자 카드 2는 카드의 존재 여부보다 빈도 관리가 핵심이다. 값별 개수를 미리 세어 두면 각 질의는 저장된 카운트를 꺼내는 일로 단순해진다.