문제 출처

1. 문제설명

  • N개 카드가 주어진다.
  • 정수 M개가 주어지고, 이 수가 적혀있는 카드가 N개의 카드에 몇 개 있는지?



2. 알고리즘 설계

  • 처음엔 이진탐색으로 접근했다가, 예제를 보니 같은 숫자가 여러 개 있었다.
    • 예제의 처음 입력을 보면 10, 10, 10이 있다.
    • 즉, 10이란 숫자는 3개가 된다.
  • 개인적으로 좋았던 풀이가 다른 블로그에 있어 가져왔다.
  • low bound, upper bound를 이용한 문제풀이 방법



3. 로직

  • 기본적으로 숫자는 정렬되어야 한다.
  • 이진탐색과 굉장히 비슷하다.
  • upper bound
    • 숫자의 마지막 부분을 찾는 것이므로, 타겟보다 커질 때까지 반복
  • lower bound
    • 중간값이 타겟값보다 크거나 같아지면 탐색 끝
    • 숫자의 첫 부분을 찾는 것이므로, 같거나 커질 때까지



4. 전체 코드

#include <bits/stdc++.h>
using namespace std;

vector<int> a;
int N, M;

int lower_bound(int target) {
    int s = 0, e = a.size() - 1;
    while (s < e) {
        int m = (s + e) / 2;
        if (a[m] >= target) e = m;
        else s = m + 1;
    }
    return e;
}
int upper_bound(int target) {
    int s = 0, e = a.size() - 1;
    while (s < e) {
        int m = (s + e) / 2;
        if (a[m] > target) e = m;
        else s = m + 1;
    }
    return e;
}

int main(void) 
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N; a.assign(N, 0);
    for (int i = 0; i < N; i++)
        cin >> a[i];
    
    sort(a.begin(), a.end());

    cin >> M;
    for (int tmp, i = 0; i < M; i++) {
        cin >> tmp;
        int lower = lower_bound(tmp);
        int upper = upper_bound(tmp);
        int ans = upper - lower;
        if (upper == N - 1 && a[N - 1] == tmp) ans++;

        cout << ans << ' ';
    }
    return 0;
}



5. 소감

  • 상한과 하한이라니.. 정말 생각지도 못한 방법이었다.
  • 해당 문제는 실버4에 랭크되었는데, 개인적으로 난이도가 좀 더 높아야 될 거 같다.