백준 10816 숫자 카드 2 / C++

문제 : 10816

풀이 point

이진 검색 or map을 활용하여 풀이를 진행할 수 있다.

map을 활용한 풀이는 아주 간단하다. 상근이가 가지고 있는 카드의 개수를 각 카드마다 map에 저장해주면 된다.

이진 검색의 경우 상근이가 가지고 있는 카드를 정렬한 뒤 탐색을 시작해야한다.

풀이 방법

카드를 정렬하였으면 중복된 숫자들을 근처에 있을 것이다. 이 중복된 숫자들의 시작과 끝이 곧 개수이다. 이것을 구하기 위해 원래의 이진 검색을 약간 변형시켜야 한다.

1 2 3 6 10 10 10 16 18
의 경우 10이 삽입되는 가장 왼쪽 인덱스는 4, 가장 오른쪽 인덱스는 7이다. 7-4 = 3이므로 중복된 숫자는 3개이다를 쉽게 구할 수 있다.

가장 왼쪽 인덱스와 오른쪽 인덱스를 구하는 법은 이진검색 글을 참고하시길

코드

//백준 1816, 숫자 카드 2

#include <iostream>
#include <algorithm>

int A[500'000];
int B[500'000];

int N, M;

int bsLeft(int i){
    int start{0}; int end{N};
    while(start < end){
        int mid = (start+end)/2;
        if(A[mid] >= B[i]) end = mid;
        else start = mid+1; 
    }
    return start;
}

int bsRight(int i){
    int start{0}; int end{N};
    while(start < end){
        int mid = (start+end)/2;
        if(A[mid] > B[i]) end = mid;
        else start = mid+1; 
    }
    return start;
}

int main (){

    std::cin >> N;
    for(int i{0}; i<N; ++i) std::cin >> A[i];
    
    std::cin >> M;
    
    for(int i{0}; i<M; ++i) std::cin >> B[i];

    std::sort(A, A+N);

    for(int i{0}; i<M; ++i){
        std::cout << bsRight(i) - bsLeft(i) << ' ';
    }
    
    return 0;
}