- 문제 링크
백준 10816번 - 숫자 카드 2
해결 전략
문제를 처음 딱 보면, 입력받은 수들을 배열로 저장하고, 배열을 Nondecreasing Order로 정렬한 다음, Binary Search(또는 Quick or Merge Sort)로 각 Target을 찾되, 찾은 요소를 미지의 플래그 변수로 가려놓고, 다시 찾고,.. 이런식으로 프로그램을 생각할 수 있다.
또는, 배열 정렬 후 똑같이 빠른 탐색을 하되, 값을 찾으면, 그 찾은 위치에서, 정렬된 배열을 좌우로 훑어 길이를 계산해서 개수를 반환하는 스타일의 알고리즘도 짤 수 있을 것이다.
하.지.만!!!
사실 이 문제는 이진탐색, 정렬, 개수 세기 등등의 작업이 "전혀" 필요없는 문제이다. 본인의 Velog 초기 PS 포스팅 문제들 중에, 이 문제에 쓰인 센스가 필요했던 문제들이 있는데, 이 포스팅들을 보고 온 다면 이 말을 단박에 이해할 수 있다.
입력받는 정수의 범위가 -10,000,000 ~ 10,000,000이다. 즉, 20,000,001개의 수를 다루고 있는 것이다. 이 '수 자체'를 배열로 바라보는 것은 어떠한가?
혹여나 이 문제를 해결하지 못해 본 포스팅에 들어온 이가 있다면, 위 문장을 읽고 무릎을 탁 쳤을 것이라 믿는다. 그렇다. 이 문제는 Pigeonhole Principle을 바탕으로 단순하게 해결할 수 있다. (배열의 사이즈는 int 기준으로 10억까진 충분하다. 그 이상도 가능.)
~> 이 방법으로 풀면, 속도면에서 상기한 알고리즘들보다 월등하게 빠르며, 공간만 좀 더 차지할 뿐이지만, 공간 제한이 넉넉하기에 문제 없다. 단순히 입력받으면서 문제를 해결해버리는 것이다.
더 이상의 자세한 설명을 불필요할 것이다. 아래는 코드이다.
#include <iostream>
// BOJ - 10816 Number Card 2
#define MAX_SIZE 500000
#define HASH_SIZE 10000000
using namespace std;
int target[MAX_SIZE + 1], cnt[2*HASH_SIZE + 1];
int main(void) {
int n, m, temp;
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> n;
for (int i = 1; i <= n; i++) { cin >> temp; cnt[temp + HASH_SIZE]++; }
cin >> m;
for (int i = 1; i <= m; i++) cin >> target[i];
for (int i = 1; i <= m; i++)
cout << cnt[target[i] + HASH_SIZE] << '\n';
return 0;
}