[C++] BOJ (백준) 10816 : 숫자 카드 2

문제

10816번: 숫자 카드 2 (acmicpc.net)

10816번: 숫자 카드 2

코드 1 (이분탐색)

#include <iostream>
#include <algorithm>

using namespace std;

vector<int> v;

int getFrequency(int num) {
  return (int) (upper_bound(v.begin(), v.end(), num) - lower_bound(v.begin(), v.end(), num));
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin >> n;
  v.resize(n);
  for (int &i: v) cin >> i;
  sort(v.begin(), v.end());

  int m;
  cin >> m;
  while (m--) {
    int num;
    cin >> num;
    cout << getFrequency(num) << ' ';
  }
  return 0;
}

 

설명

벡터에 n개의 정수를 입력받은 후 정렬한다.
그 후, 찾으려 하는 정수마다 std::lower_bound(이상인 최초의 값)과
std::upper_bound(초과인 최초의 값)의 인덱스 차이를 출력하면 된다.

int lowerBound(int num) {
  int low = 0;
  int high = n;
  while (low != high) {
    int mid = (low + high) / 2;
    if (v[mid] < num) low = mid + 1;
    else high = mid;
  }
  return low;
}

int upperBound(int num) {
  int low = 0;
  int high = n;
  while (low != high) {
    int mid = (low + high) / 2;
    if (v[mid] <= num) low = mid + 1;
    else high = mid;
  }
  return low;
}

lower_bound, upper_bound는 위와 같이 구현할 수 있다.

 

코드 2 (HashMap)

#include <iostream>
#include <unordered_map>

using namespace std;

unordered_map<int, int> mp;

void updateFrequency(int num) {
  if (!mp.contains(num)) mp[num] = 1;
  else mp[num]++;
}

int getFrequency(int num) {
  if (!mp.contains(num)) return 0;
  return mp[num];
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin >> n;
  while (n--) {
    int num;
    cin >> num;
    updateFrequency(num);
  }

  int m;
  cin >> m;
  while (m--) {
    int num;
    cin >> num;
    cout << getFrequency(num) << ' ';
  }
  return 0;
}

설명

HashMap인 std::unordered_map을 사용하면 삽입과 탐색 연산을 평균적으로 O(1)에 할 수 있어 굉장히 빠르다.
TreeMap인 std::map을 사용해도 통과는 되지만 삽입과 탐색 연산이 O(log n)이라 unordered_map 보다는 느리다.

 

코드 3 (Counting Sort)

#include <iostream>

#define MIN_NUM (-10000000)
#define MAX_NUM 10000000

using namespace std;

int arr[MAX_NUM - MIN_NUM + 1];

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin >> n;
  while (n--) {
    int num;
    cin >> num;
    arr[num - MIN_NUM]++;
  }

  int m;
  cin >> m;
  while (m--) {
    int num;
    cin >> num;
    cout << arr[num - MIN_NUM] << ' ';
  }
  return 0;
}

설명

정확히 말하면 Counting Sort를 그대로 적용한 것은 아니고 아이디어만 가져온 것이다.
2천만+1개 사이즈의 배열을 만든 후 입력받은 숫자에 해당하는 위치의 값을 올린다.
메모리 제한은 256MB인데, 2천만 * 4byte (int) = 8천만 byte = 약 80MB이므로 충분히 가능하다.