[BOJ] 10816번: 숫자 카드 2

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

상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 하는 M개의 숫자를 쿼리라고 부르겠습니다. N개의 리스트에서 a라는 원소가 몇 개 있는지 구하는데 걸리는 시간은 O(N)이기 때문에 각 쿼리를 독립적으로 처리하면 O(NM)으로 절대 시간내로 통과할 수 없습니다.

대신 숫자 카드와 쿼리를 각각 크기 순으로 정렬한 후, merge sort에서 merge를 하는 것과 같은 방식으로 인덱스를 두고 작은 수에서 큰 수로 읽어나가면서 현재 인덱스에서

i) 숫자 카드에 적힌 값이 쿼리에 적힌 값보다 작을 경우 다음 숫자카드를 보고

ii) 쿼리에 적힌 값이 숫자 카드에 적힌 값보다 작을 경우 다음 쿼리를 보고

iii) 숫자 카드에 적힌 값과 쿼리에 적힌 값이 같을 경우 쿼리에 대한 정답을 1 증가시키고 다음 숫자카드를 봄

이걸 반복하면 됩니다. 구현이 크게 어렵지는 않으나 M개의 수 중에서 중복된 수가 있을수도 있다는 것을 망각해서 여러번 틀렸습니다.

https://github.com/encrypted-def/BOJ/blob/master/10816.cpp