[C++] 백준 알고리즘 10816 숫자 카드 2 (이분 탐색)

10816번: 숫자 카드 2 (acmicpc.net)

10816번: 숫자 카드 2

(이분 탐색) 지난 포스팅 을 통해 이분 탐색을 공부했다.

이번엔 직접 구현을 해보았다.

 

우선 해당 문제는 내가 원하는 카드가 몇 장 있는지 탐색해야하는 문제인데, 어떻게 구할까?

 

이 문제에서는 upperBound 와 lowerBound 에 대해 알아야한다.

[ 1 2 2 2 3 ] 라는 배열이 있다고 했을 때, 2를 찾는다고 가정해보자.

lowerBound는 내가 찾는 카드의 가장 작은 인덱스 (여기서는 1) 를 의미하고

upperBound는 내가 찾는 카드의 가장 큰 인덱스 + 1을 한 값을 의미한다. (여기서는 4)

그리고 upperBound - lowerBound를 해준다 그러면 3이라는 값이 나오는데, 이 값이 같은 숫자 카드들의 갯수이다.

---

upperBound와 lowerBound를 구해보자.

 

우선 lowerBound는 가장 작은 인덱스를 구하면 된다.

그러므로 만약 내가 찾고자 하는 숫자가 mid 위치와 같거나 작으면 right를 옮겨준다.

1. (찾고자 하는 값이) mid와 같을 경우 = 더 왼쪽에 같은 숫자가 있으면 왼쪽으로 가야한다.

그러므로 현재 mid값 보다 하나 작은 위치로 right를 이동한다. 그러므로 right = mid - 1; 을 한 것이다.

근데 이동했는데 다른 숫자가 있으면? mid -1 한 값에 다른 숫자가 있는 것이고, mid 값에는 찾는 숫자가 있는 것이니 mid 값이 lowerBound 이다.

즉 mid 값인 right + 1을 리턴해주자!!

2. (찾고자 하는 값이) mid 보다 작은 경우 = 1~100 중 50을 불렀는데 down이라고 한 상황이 된 것이다. 그러면 1~49를 탐색해야한다. 그러므로 right = mid - 1; 을 한 것이다.

+ (찾고자 하는 값이) mid 보다 큰 경우 = 1~100 중 50을 불렀는데 up이라고 한 상황이 된 것이다. 그러면 51~100을 탐색해야한다. 그러므로 left = mid + 1; 을 한 것이다.

---

upperBound도 비슷하다. 찾고자 하는 값이 mid보다 작으면 right를 mid보다 작은 값으로 옮겨주면 된다.

그런데 mid와 같거나 mid보다 크면 생각을 해봐야한다.

1. (찾고자 하는 값이) mid와 같을 때 = 해당 mid 오른쪽에 같은 수가 더 있나? 생각해봐야한다.

2. (찾고자 하는 값이) mid보다 클 때 = left를 mid 다음 값으로 넘겨주자.

여기서는  왜 리턴 right + 1을 할까?

현재 right값은 해당 수의 가장 뒷 번호 index를 가리키게 된다.

upperBound는 그 index + 1 값이니 right +1를 한 것이다.

left가 right를 벗어나는 순간 while이 종료되므로 right + 1 은 곧 left와도 같다. return left 해도 된다.

 

말로 하려니 복잡하지만 그림을 그려보거나 관련 애니메이션을 보면 바로 이해가 될 수도 있다!

추가적으로... 이분 탐색은 정렬이 되어있어야만 가능하다. 꼭 정렬을 하자!! (2번이나 까먹음)

 

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

using namespace std;

vector<int> card;

// 같은 숫자가 있다면, 그 수들을 가리키는 가장 작은 인덱스 반환
int lowerBound(int left, int right, int num){
    while(left<=right){ // left가 right를 넘어가는 순간 종료
        int mid = (left + right) /2 ;
        if(card[mid]>=num) //찾는 숫자랑 동일하면, 왼쪽에 같은 수가 더 있는지 확인해보자
            right = mid -1;
        else
            left = mid +1;
    }
    return right + 1;
    //  arr[mid]가 찾는 수와 같을 때, 이 위치보다 왼쪽에 같은 수가 있는지 확인했는데, 이때...
    // right = mid -1을 했으므로... 왼쪽에 같은 수가 없으면 mid 값, 즉 right + 1이 lowerBound 이다
}

// 같은 숫자가 있다면, 그 수들을 가리키는 가장 큰 인덱스 + 1 의 값 반환
int upperBound(int left, int right, int num){
    while(left<=right){
        int mid = (left + right) /2;
        if(card[mid] > num)
            right = mid -1;
        else // 찾는 수와 같거나 더 작은 수를 탐색 중이었다면...
        //1. 찾는 수와 동일한 수 였으면 오른쪽에 같은 수가 있는지 찾아야함
        //2. 더 작은 수를 탐색 중이었다면, mid값보다 크다는 의미이니 left를 mid보다 큰 값으로 설정
            left = mid +1;
    }
    return right + 1;
    //현재 right값은 해당 수의 가장 뒷 번호 index를 가리킴. upperBound는 그 index + 1 값이니 right +1...
    //left가 right를 벗어나는 순간 while이 종료되므로 right + 1 은 곧 left와도 같다. return left 해도됨
}

int main(){
    //입출력향상. 없으면 시간초과
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    cin>>n;
    card.assign(n,0);
    for(int i=0; i<n; i++)
        cin>>card[i];

    sort(card.begin(), card.end()); // 이분 탐색 정렬 필수!!

    int m, temp;
    cin>>m;
    for(int i=0; i<m; i++){
        cin>>temp;
        cout<<upperBound(0, n-1, temp)- lowerBound(0, n-1, temp)<<' ';
    }
}