[백준 10816] 알고리즘 54일차 : 숫자 카드 2

www.acmicpc.net/problem/10816

10816번: 숫자 카드 2

이분탐색 C++

입력받은 숫자배열에 또 다른 배열에 주어진 숫자들이 몇개씩 포함되어있는지 출력하는 문제 (이과생의 글솜씨 ㅈㅅ)

숫자를 찾은 후에 숫자 개수를 하나씩 세어나가면 안된다. 이유는 모두 같은 수 일때는 결국 전체탐색을 하게 되기 때문.

그래서 lower_bound랑 upper_bound를 구해서 풀어야 하는 문젠데 구현 다 했는데 계속 시간초과 나서 찾아보니까

STL이 있었다. 그래서 써봤는데 그것도 안돼서

ios::sync_with_stdio(false);

cin.tie(0);

이 구문들 썼더니 바로 해결됐다.

그 후에 내가 구현한 함수들로 다시 제출하니까 그것도 시간초과 없이 통과됐다. (..^^)

 

소스코드

#include <iostream>
#include <algorithm>
using namespace std;
int gotnum[500000];
int N;

int binarySearchS(int num){
    int s = 0;
    int e = N-1;
    int mid = (s+e)/2;
    while(e>=s){
        mid = (s+e)/2;
        if(gotnum[mid] == num && gotnum[mid-1] != num){
            return mid;
        }
        else if(gotnum[mid] >= num){
            e = mid-1;
        }
        else{
            s = mid+1;
        }
    }
    return N;
}
int binarySearchE(int num){
    int s = 0;
    int e = N-1;
    int mid = (s+e)/2;
    while(e>=s){
        mid = (s+e)/2;
        if(gotnum[mid] == num && gotnum[mid+1] != num){
            return mid;
        }
        else if(gotnum[mid] <= num){
            s = mid+1;
        }
        else{
            e = mid-1;
        }
    }
    return -1;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> N;
    for(int i = 0 ; i < N ; i++){
        cin >> gotnum[i];
    }
    sort(gotnum, gotnum+N);
    
    int M;
    cin >> M;
    
    int setnum,cnt;
    for(int i = 0 ; i < M ; i++){
        cin >> setnum;
        cnt = binarySearchE(setnum)-binarySearchS(setnum)+1;
        if(cnt < 0)
            cnt = 0;
        cout << cnt << " ";
    }
    return 0;
}

코드 좀 지저분한거 아는데 지금 이거에 시간을 너무 쓴 것 같아서 넘어갈게요..