[백준] 10816: 숫자 카드 2

처음 생각은, 카드를 입력받으면서 카드 개수도 같이 세주는 것을 생각했는데, 카드 개수를 세기 위해서는 매번 위치를 찾아야해서 여기서 시간초과가 계속 뜬 듯 하다. 해법은 이진탐색을 이용해서, 일단 입력 받은 후에, sortinng 하고 lowerboudn, upperbounnd찾는것.

내가 짠 코드

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

vector<int> deck;
int N;


int upperBound(int value);
int lowerBound(int value);
int main(void){
    
    int i,value,idx;
    int upper,lower;

    scanf("%d",&N);

    for(i=0;i<N;i++){
        scanf("%d",&value);
        deck.push_back(value);
    }
    sort(deck.begin(),deck.end());
    
    int M;
    scanf("%d",&M);
    for(i=0;i<M;i++){
        scanf("%d",&value);
        upper = upperBound(value);
        lower = lowerBound(value);

        if(deck[lower]==value){
            idx = upper - lower + 1;
        }
        else idx = 0;

        printf("%d ",idx);
    }
    printf("\n");
    return 0;
}
int upperBound(int value){
    int s,e,m;
    s=0;
    e=N-1;

    while(e-s > 0){
        m = (s+e)/2;
        if(deck[m] <=value) s= m+1;
        else e=m;
    }

    if(deck[e] !=value) e --;

    return e;
}
int lowerBound(int value){
    int s,e,m;
    s=0;
    e=N-1;

    while(e-s > 0){
        m = (s+e)/2;
        if(deck[m] <value) s= m+1;
        else e=m;
    }

    return e;
}

시간 초과 된 코드

C++ 의 map을 이용해서 접근했는데 시간초과가 뜬다. 이것이 뭔 일이람.

#include<iostream>
#include<map>
#include<algorithm>

using namespace std;

int main(void){
    
    int N,i,value;

    scanf("%d",&N);

    map <int, int> deck;

    for(i=0;i<N;i++){
        scanf("%d",&value);
        if(deck.count(value)==0) deck.insert(make_pair(value,1));
        else deck[value]++;
    }
    scanf("%d",&N);
    for(i=0;i<N;i++){
        scanf("%d",&value);
        printf("%d ",deck[value]);
    }
    printf("\n");
    return 0;
}

시간 초과 된 코드 2

C++ 벡터를 2개 사용해서 value, count값을 저장했는데 여전히 시간초과.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main(void){
    
    int N,i,value,idx;
    vector<int> deck;
    vector<int> count;
    vector<int>::iterator iter;

    scanf("%d",&N);

    

    for(i=0;i<N;i++){
        scanf("%d",&value);
        iter = find(deck.begin(),deck.end(),value);
        if(iter<deck.end()){ //이미 있다면
            idx = iter - deck.begin();
            count[idx]++;
        }
        else {
            deck.push_back(value);
            count.push_back(1);
        }
    }
    scanf("%d",&N);
    for(i=0;i<N;i++){
        scanf("%d",&value);
        iter = find(deck.begin(),deck.end(),value);
        if(iter<deck.end()){
            idx = iter - deck.begin();
            printf("%d ",count[idx]);
        }
        else printf("0 ");
    }
    printf("\n");
    return 0;
}

www.acmicpc.net/problem/10816

10816번: 숫자 카드 2