문제

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

내 접근

1. 입력되는 숫자가 중복이 있을 수 있네, std::vector에서 인덱스를 카드 숫자로 높고 카운팅을 해야할까? -> 카드 숫자의 범위가 -10,000,000부터 10,000,000 이니까 메모리 비용이 클 것 같다.
2. 정렬 조건은 딱히 필요 없는 것 같으니 std::unordered_map를 사용할 수 있겠다. 키는 카드 숫자로, 값은 카운팅으로
3. std::unordered_map을 쓰는게 맞을까? 그냥 std::map을 쓰면 어떻게 되지? 전에 파악한 find, erase 등의 메서드의 평균 시간복잡도가 O(log n)이라고 했던 것 같은데, n과 m이 최대 5 x 10^5 이고, 처음 카드 숫자를 map에 넣을 때 그 숫자가 이미 있는지 판단해야하니까 n 만큼 find 해야한다면, 입력 과정에서 O(n log K) 만큼 연산 시간이 걸릴 것 같은데? 출력에서도 m만큼 find 해야하니까 O(m log K)만큼 걸리는건가? 계산 해보면 log_2(5 x 10^5)가 5.7이 나오고 n과 m 모두 동일하니까 2.85 x 10^6이 나오는데, 이만큼 연산해야한다는건가?

구현

#include <iostream>
#define IO std::cin.tie(NULL), std::ios_base::sync_with_stdio(false)

#include <unordered_map>

void solve() {
  int n, m;

  std::cin >> n;

  std::unordered_map<int, int> counts;

  int x;
  for (int i = 0; i < n; i++) {
    std::cin >> x;
    auto it = counts.find(x);
    if (it != counts.end()) {
      it->second++;
    } else {
      counts.insert({x, 1});
    }
  }

  std::cin >> m;
  for (int i = 0; i < m; i++) {
    std::cin >> x;
    auto it = counts.find(x);
    if (it != counts.end()) {
      std::cout << it->second << ' ';
    } else {
      std::cout << 0 << ' ';
    }
  }
}

int main() {
  IO;
  solve();
  return 0;
}

다른 접근 방법

정렬, 이진 탐색

• 카드 숫자 배열을 정렬
• 각 숫자 카드 질의마다 lower_bound, upper_bound를 구해서 upper_bound - lower_bound로 개수를 구한다

복잡도

• 정렬할 때: O(N log N)
• 질의할 때: O(M log N)
• 공간: O(N)

sort(cards)
for q in queries:
  l = lower_bound(cards, q)
  r = upper_bound(cards, q)
  print(r - l)

좌표 압축 + vector 카운팅

• 카드 + 질의 값 모두 모아서 정렬
• 값 → 압축 인덱스
• vector<int>로 카운팅

복잡도

• 압축: O((N+M) log (N+M))
• 이후 연산: O(N + M)
• 공간: O(N + M)

values = cards + queries
sort(unique(values))
map value -> index

count[index(card)]++
for q in queries:
  print(count[index(q)])