백준 10816번: 숫자 카드2

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

10816번: 숫자 카드 2

 

이 문제는 보통 방법으로 풀면 시간 초과가 난다. 이분탐색을 이용해

중복된 값에서 첫 위치와 끝 위치를 구하는게 중요하다.(시간초과로 고생한건 안비밀..)

어쨋든 값진 경험이라 블로그에 남긴당

이 문제를 풀면서 upper_bound와 rower_bound 에 대해서 알게 되었다. 

둘 다 정렬을 기본 전제로 간다.

그냥 간단하게 upper_bound 는 중복된 값 중에서 마지막 원소 값을 가리키는 인덱스 반환

rower_bound 는 중복된 값 중에서 첫번째 원소 값을 가리키는 인덱스 반환이다.

그리고 이를 빠르게 참조하기위해 이분탐색을 이용한다.

일단 rower_bound

int rower_bound(vector<int> &v1,int target,int size){ //탐색 중복 값 중 가장 맨 앞쪽 출력
    int start=0;
    int end=size-1;
    int mid;
    while(end>start){
        mid=(start+end)/2;
        if(v1[mid]>=target){  //중복된 값들은 다 end에 넣음 이러면 중복 된 값이 걸려도 mid 값은 앞으로 가면서 맨앞으로 가게됨
            end=mid;
        }
        else{
            start=mid+1;
        }
    }
    return end;
}

upper_bound

int upper_bound(vector<int> &v1,int target, int size){  //중복된 값 바로 다음 값 위치 찾기
    int start=0;
    int end=size-1;
    int mid;
    while(end>start){
        mid=(start+end)/2;
        if(v1[mid]>target){   //탐색 값이 타겟 값보다 크면 끝을 중간값 넣기 즉, 탐색값 보다 큰 다음 값 위치로 맞추어짐
            end=mid;
        }
        else{
            start=mid+1;
        }
    }
    return end;
}

 

 upper_bound에서 중복된 값 다음 인덱스를 가리키는 함수다

헷갈리면 안되는 것은 start=mid+1은 필수 이다. mid값이 나누기 2로 구해지는데 3/2=1이 듯이 1.5에서 내림으로 받는다.즉 end에서 -1은 안해도 나누면 저절로 내려가지는데 start는 +1을 안하면 잘못하다가는 무한루프에 빠지게 된다.

 

저 upper_bound에서 한가지 예외가 존재하는데 그것은 마지막 중복 인덱스 값이다.마지막은 그 다음 인덱스를 가리킬수 없으므로 예외처리를 해줘야 한다. 코드를 봅시당

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> v;
int upper_bound(vector<int> &v1,int target, int size){  //중복된 값 바로 다음 값 위치 찾기
    int start=0;
    int end=size-1;
    int mid;
    while(end>start){
        mid=(start+end)/2;
        if(v1[mid]>target){   //탐색 값이 타겟 값보다 크면 끝을 중간값 넣기 즉, 탐색값 보다 큰 다음 값 위치로 맞추어짐
            end=mid;
        }
        else{
            start=mid+1;
        }
    }
    return end;
}

int rower_bound(vector<int> &v1,int target,int size){ //탐색 중복 값 중 가장 맨 앞쪽 출력
    int start=0;
    int end=size-1;
    int mid;
    while(end>start){
        mid=(start+end)/2;
        if(v1[mid]>=target){  //중복된 값들은 다 end에 넣음 이러면 중복 된 값이 걸려도 mid 값은 앞으로 가면서 맨앞으로 가게됨
            end=mid;
        }
        else{
            start=mid+1;
        }
    }
    return end;
}

int main(){
    cin.tie(NULL);
	cout.tie(NULL);
	ios_base::sync_with_stdio(false);
    int n,m;
    cin>>n;
    int t;
    for(int i=0;i<n;i++){
        cin>>t;
        v.push_back(t);
    }
    sort(v.begin(),v.end());
    cin>>m;
    for(int i=0;i<m;i++){
        cin>>t;
        int start =rower_bound(v,t,n);
        int end=upper_bound(v,t,n);
        if(end==n-1&&v[end]==t){     // 마지막 값이 중복되면 upper_bound가 그 다음 위치를 못 가져오므로 예외처리
            end++;
        }
        cout << end-start<<' ';
    }
}