[Baekjoon,10816]숫자 카드 2

해결

시작하기에 앞서 이 문제는 입출력이 많기 때문에 cin, cout 보다 빠른 방식을 택해야 한다.

1. map container 이용

map을 이용하여 각 숫자 카드의 값이 key에 존재하면 증가시키고 없다면 map에 추가하는 방식으로 진행했다.

#include <iostream>
#include <map>
using namespace std;

int main()
{
    map<int,int> amount;
    int N,M;
    
    cin>>N;
    for(int i=0;i<N;++i)
    {
        int num;
        scanf("%d",&num);
        // 해당 값이 있으면 1을 더한다. 
        if(amount.insert(make_pair(num, 1)).second == false)
            amount[num]+=1;
    }
    
    cin>>M;
    for(int i=0;i<M;++i)
    {
        int num;
        scanf("%d",&num);
        
        /////////////////////////////////////////////
        // 시간초과를 받는 방법 
        //printf("%d ",amount[num]);
        /////////////////////////////////////////////
        
        map<int,int>::iterator it=amount.find(num);
        if(it==amount.end())
            printf("0 ");
        else
            printf("%d ",it->second);
    }
    return 0;
}

주석으로 표시한 방법은 시간초과를 받았다. 왜냐하면 map의 [] 연산은 해당 key가 없을 때 디폴트 값인 0을 value에 삽입하기 때문에 최악의 경우 1,000,000개의 원소가 삽입될 수 있기 때문이다. 또한 []연산은 느리기 때문에 코드처럼 find 함수로 찾아보고 있다면 해당 iterator 위치의 value를 출력해야 한다. []연산이 느린 이유는 스피비 블로그에서 알게 되었다.

[] 연산자는 보통의 포인터 연산이 아닌 양방향으로 순회하여
찾는 방법이기 때문에 찾는 속도가 느릴 수 있다.

2. 이분 탐색 이용

더욱 빠르고 메모리를 덜 차지하는 방법은 바로 이분 탐색을 이용하는 것이다. 모든 값을 입력 받아 정렬한 뒤 이분 탐색을 이용하여 해당 값의 위치와 해당 값보다 큰 제일 앞 원소의 위치를 비교하면 결과를 얻을 수 있다.

구현 시 맨 앞의 값과 맨 뒤의 값을 각각 음의 무한대, 무한대로 설정한 것을 볼 수 있다. 물론 이를 직접 구현하지 않고 lower_bound 함수를 이용하여 다르게 해결할 수도 있다.

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;

const int INF=10000001;
const int MAX=500000+2;

int N,M;
int perm[MAX];

int lowerBound(int num)
{
    int lo=0, hi=N-1;
    while(lo!=hi-1)
    {
        int mid=(lo+hi)/2;
        if(perm[mid]<num)
            lo=mid;
        else
            hi=mid;
    }
    return hi;
}

int main()
{
    cin>>N;
    N+=2;
    for(int i=2;i<N;++i)
        scanf("%d",&perm[i]);
    
    perm[0]=-INF;
    perm[1]=INF;
    sort(perm, perm+N);
    
    cin>>M;
    for(int i=0;i<M;++i)
    {
        int num;
        scanf("%d",&num);
        
        int lo=lowerBound(num);
        int hi=lowerBound(num+1);
        
        printf("%d ",hi-lo);
    }
    return 0;
}