[C++] 백준 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개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

구상

숫자와 그 숫자의 개수를 key와 value 쌍으로 생각하여 map 컨테이너로 파악한다.

//입출력 속도 높이기
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

C++의 입출력 함수는 상당히 느린 편인데, 엄청나게 많은 입출력을 받아야 하는 백준 문제에서 활용하려면 

파이썬에서 sys.stdin을 쓰듯이 입출력 속도를 높여줘야 시간 초과 에러가 발생하지 않는다. 위의 세 줄은 입출력 함수끼리 연결을 해제하여 동작을 빠르게 한다. 

 

for (int i = 0; i < size; i++) {
	cin >> num;
	if (number.find(num) == number.end())	//일치하는 항목 없으면
		number[num] = 1;	//새로운 인자를 만들고 카운트는 1
	else number[num]++;	//항목이 있으면 카운트 + 1
}

map은 STL로 반복자(iterator)를 지원한다.

find 메서드는 키가 일치하는 항목의 값을 리턴하는데, 키가 없으면 end 반복자를 리턴한다.

 

일치하는 숫자가 없다면, 즉 end를 리턴하면 새로운 키로 수를 집어넣고 값에는 1을 넣는다. 숫자가 1번 입력되었다는 뜻이다.

일치하는 숫자가 있다면 해당하는 키의 값을 1 증가시켜 개수를 센다.

for (int i = 0; i < size; i++) {
	cin >> num;
	if (number.find(num) == number.end())	//일치하는 항목 없으면
		cout << 0 << " ";	//0과 공백 출력
	else cout << number[num] << " ";	//있으면 개수와 공백 출력
}

같은 논리로 출력한다. 일치하는 수가 없으면 0을, 있으면 개수를 출력하는데 문제에서 공백으로 구분하라 했으므로 끝에 공백을 추가해 출력한다.

코드

#include <iostream>
#include <map>

using namespace std;

int main(void)
{
	//입출력 속도 높이기
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	map <int, int> number;
	int size, num;

	cin >> size;
	for (int i = 0; i < size; i++) {
		cin >> num;
		if (number.find(num) == number.end())	//일치하는 항목 없으면
			number[num] = 1;	//새로운 인자를 만들고 카운트는 1
		else number[num]++;	//항목이 있으면 카운트 + 1
	}

	cin >> size;
	for (int i = 0; i < size; i++) {
		cin >> num;
		if (number.find(num) == number.end())	//일치하는 항목 없으면
			cout << 0 << " ";	//0과 공백 출력
		else cout << number[num] << " ";	//있으면 개수와 공백 출력
	}
	return 0;
}

 

참고

빠른 입출력: https://ansohxxn.github.io/cpp/iospeed/

<map>: https://blockdmask.tistory.com/87