(매일 BOJ) C++ 10816번 숫자카드 2

이번 문제는 백준 10816번 숫자카드 2 문제이다.

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

 

문제의 접근법부터 생각해보자

백준 10816번 "숫자 카드 2" 문제는 주어진 N개의 숫자 카드에 대해, M개의 숫자가 각각 몇 개씩 존재하는지를 빠르게 찾아야 하는 문제다.

 

그렇다 필자는 이 문제에서도 뇌를 빼고 풀다가 시간초과가 뜨는 말하는 감자였다.

지금까지 필자가 ps 약 160여 문제를 풀면서 시간 초과가 뜬 적이 별로 없었는데,오늘 하루에만 시간초과가 3번 뜨는 것을 보니 c++이 나랑 안맞는건지, 파이썬에서 무의식적으로 시간복잡도를 기가막히게 분석하며 풀었던 것인지 도통 모르겠다.

 

아래가 필자가 처음 풀었던 코드이다.

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

int main(void){
    ios::sync_with_stdio(0); cin.tie(0);
    int N,M;
    cin >> N;
    vector<int> v(N);
    for (int i = 0; i < N; i++){
        cin >> v[i];
    }

    cin >> M;
    for (int j = 0; j < M; j++){
        int cnt = 0, target = 0;
        cin >> target;
        cnt = count(v.begin(),v.end(),target);
        cout << cnt << " ";
    }

    return 0;
}

 

이 문제는 필자처럼 단순하게 count()를 사용하면 시간 초과가 발생하기 때문에, 효율적인 접근이 필요하다.

가장 일반적인 방법은 입력 받은 N개의 수를 정렬한 뒤, lower_bound와 upper_bound를 이용해 각 숫자의 등장 범위를 이분 탐색으로 찾아 개수를 계산하는 방식이 존재할 것이다.

아니라면  unordered_map을 사용해 각 숫자의 등장 횟수를 미리 기록해 두고, 질의 숫자에 대해 O(1)에 가까운 시간으로 결과를 출력하는 방법도 효율적이다.

 

가장 일반적인 방법으로 코드를 수정해보았다.

이 문제에서는 그 유명한 이분탐색 알고리즘이 사용되고 있다. 

이분 탐색이란?

이분 탐색(Binary Search)은 정렬된 배열에서 원하는 값을 반씩 줄여가며 찾는 탐색 알고리즘이다.

 선형 탐색(완전탐색 ex) 브루트포스)이 맨 앞부터 끝까지 확인하는 반면, 이분 탐색은 중간부터 시작해서 범위를 절반씩 좁히는 방식으로 탐색한다.

process

1. 시작점(left)과 끝점(right)을 설정
2. 중간점(mid)을 계산: mid = (left + right) / 2
3. 중간값과 찾는 값을 비교
   - 같으면 종료
   - 작으면 오른쪽으로 탐색 범위 이동 (left = mid + 1)
   - 크면 왼쪽으로 탐색 범위 이동 (right = mid - 1)
4. left > right가 되면, 탐색 실패

 

시간 복잡도

• 범위를 매 단계마다 절반으로 줄이기 때문에,
• 최대 비교 횟수는 log₂(N)번 → O(log N)

예:

• 1,000개 → 약 10번
• 1,000,000개 → 약 20번
• 1,000,000,000개 → 약 30번

선형 탐색의 O(N)에 비해 훨씬 빠르다.

⚠️ 주의사항

• 배열이 반드시 정렬되어 있어야 함
• 정렬되지 않은 배열에선 이분 탐색이 틀린 결과를 낼 수 있음

 

그럼 이분탐색을 사용해서 이 코드를 다시 수정해보자.

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

int main(void){
    ios::sync_with_stdio(0); cin.tie(0);
    int N,M;
    cin >> N;
    vector<int> v(N);
    for (int i = 0; i < N; i++){
        cin >> v[i];
    }
    sort(v.begin(),v.end());
    cin >> M;
    for (int j = 0; j < M; j++){
        int cnt = 0, target = 0;
        cin >> target;
        int lower = lower_bound(v.begin(), v.end(), target) - v.begin();
        int upper = upper_bound(v.begin(), v.end(), target) - v.begin();
        cnt = upper - lower;
        cout << cnt << " ";
    }

    return 0;
}