[BOJ/C++] 숫자 카드 2(10816번)

1. 개요

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

10816번: 숫자 카드 2

1-1. 설명

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

1-2. 제한 사항

 - 첫 줄에는 상근이가 지닌 숫자 카드 개수 N이 주어지며, N은 1 이상 500,000 이하 자연수

 - 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어지며, 숫자 카드에 적혀있는 수는 -10,000,000 이상 10,000,000 이하

 - 셋째 줄에는 M이 주어지며, M은 1 이상 500,000 이하

 - 넷째 줄에는 상근이가 몇개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어짐. 이 수도 둘째 줄 카드 수 범위와 동일

---

2. 구현

2-1. 풀이

무턱대고 수를 정렬하여 for문을 돌려 세아리면 시간 초과가 나게된다. 상근이의 수를 받아 배열 인덱스의 값으로 넣은 다음 +1을 해주고, M개의 카드 정수에 대해서는 인덱스를 출력하게끔 하였다. 배열의 인덱스에서는 음의 정수는 배열의 뒷부분으로 인식하므로, NEGA_NUM을 통해 음의 정수가 들어왔을 땐 NEGA_NUM을 더하여 10,000,000 인덱스부터 시작하게끔 하였다. 

2-2. 코드

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

constexpr size_t MAX_NUM = 20000001;
constexpr size_t NEGA_NUM = 10000000;
int nums[MAX_NUM];

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

	int N, M, num;
	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> num;
		if (num >= 0) {
			nums[num]++;
		}
		else {
			nums[abs(num) + NEGA_NUM]++;
		}
	}

	cin >> M;
	for (int i = 0; i < M; i++) {
		cin >> num;
		if (num >= 0) cout << nums[num] << ' ';
		else cout << nums[abs(num) + NEGA_NUM] << ' ';
	}

	return 0;
}