[이분탐색] 숫자 카드2 (백준 10816번)

일단 첫번째로 올린 코드는 잘못된 코드다.

46%에서 시간초과로 끝나는 것을 확인할 수 있다, 이전 이분 탐색 문제에서는 내가 제시한 방법으로 시간초과를 해결했지만 이 문제에서는 같은 방법으로 해도 46%까지 밖에 안 되는 거로 보아 더 획기적인 해결 방법이 필요한 듯 하다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int n, m;
// int target[500000];
vector <long long int> target;
vector <long long int> answer;
// long long int answer[500001];
 
int counted = 0;
int lPos;
int rPos;
 
void PreCount(int pos, int targeting)
{
    //    if (targeting == target[pos - 1])
    //    {
    //        counted++;
    //        PreCount(pos - 1, targeting);
    //    }
 
    while (targeting == target[pos - 1])
    {
        counted++;
        pos--;
        if (pos - 1 < 0)
            break;
    }
    lPos = pos;
}
 
void AfterCount(int pos, int targeting)
{
    //    if (targeting == target[pos + 1])
    //    {
    //        counted++;
    //        AfterCount(pos + 1, targeting);
    //    }
 
    while (targeting == target[pos + 1])
    {
        counted++;
        pos++;
        if (pos + 1 >= n)
            break;
    }
    rPos = pos;
}
void binarySearch(int left, int right, int targeting)
{
    int mid = (left + right) / 2;
    if (left > mid) return;
    if (targeting == target[mid])
    {
        lPos = mid;
        rPos = mid;
        counted = 1;
        if (mid - 1 >= 0
            && targeting == target[mid - 1]) PreCount(mid, targeting);
 
        if (mid + 1 < n
            && targeting == target[mid + 1]) AfterCount(mid, targeting);
 
        //        target.erase(target.begin() + lPos, target.begin() + rPos);
        //        n -= counted;
        return;
    }
 
    if (targeting < target[mid])
        binarySearch(left, mid - 1, targeting);
    else if (targeting > target[mid])
        binarySearch(mid + 1, right, targeting);
}
 
int main(void)
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        long long int num;
        scanf("%lld", &num);
 
        target.push_back(num);
    }
    sort(target.begin(), target.end());
 
    scanf("%d", &m);
    for (int i = 0; i < m; i++)
    {
        long long int num;
        scanf("%lld", &num);
 
        answer.push_back(num);
    }
 
    for (int i = 0; i < m; i++)
    {
        //        counted = 0;
        lPos = rPos = -1;
 
        if (n - 1 > 0
            && answer[i] > target[n - 1] || answer[i] < target[0])
        {
            printf("0 ");
            continue;
        }
 
        else
        {
            binarySearch(0, n - 1, answer[i]);
            if (lPos == -1 && rPos == -1)
                printf("0 ");
 
            else printf("%d ", rPos - lPos + 1);
 
        }
    }
}

 

그래서 다시 만들었다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int n, m;
// int target[500000];
vector <long long int> target;
vector <long long int> answer;
// long long int answer[500001];
 
int counted = 0;
int lPos;
int rPos;
 
int lower_bound(int num, int targeting) // targeting과 같은 수가 등장할 때 마지막 인덱스
{
    int start = 0;
    int end = n;
    int mid = n;
 
    while (end - start > 0) // end와 start 사이에 탐색할 게 남아 있다면,
    {
        mid = (end + start) / 2;
 
        if (target[mid] < targeting)
            start = mid + 1;
        else
            end = mid;
    }
    
    return end + 1;
}
 
int upper_bound(int num, int targeting) // targeting과 같은 값이 등장하는 첫 인덱스 찾기
{
    int start = 0;
    int end = n;
    int mid = n;
 
    while (end - start > 0) // end와 start 사이에 탐색할 게 남아 있다면,
    {
        mid = (end + start) / 2;
 
        if (target[mid] <= targeting) // '=' 하나 차이로 달라진다.
            start = mid + 1;
        else
            end = mid;
    }
 
    return end + 1;
}
 
// 1 2 3 4 5 5 5 5 6 7이라는 총 10개의 수 중에서 5를 타겟팅한다고 해보자,
// 첫 mid는 4번 인덱스 (value = 5가 나온다.)
// lower_bound는 end를 mid로 옮기기 때문에 0과 4번 인덱스 사이의 탐색을 진행하고,
// upper_bound는 start를 옮기기 때문에 start를 4 + 1번, 즉 5번 인덱스로 옮겨 5번과 9번 사이를 탐색한다.
 
// lower는 찾았을 때 end를 옮겨서 뒤를 지나쳐서 더 이상 targeting을 찾을 수 없는 지점의 end + 1 지점,
// 즉 처음으로 targeting이 등장하는 지점을 찾고,
// upeer는 start가 옮겨지기 때문에 마지막 지점을 찾아서 end + 1을 반환한다. (end는 마지막 mid를 담고 있다.)
 
int main(void)
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        long long int num;
        scanf("%lld", &num);
 
        target.push_back(num);
    }
    sort(target.begin(), target.end());
 
    scanf("%d", &m);
    for (int i = 0; i < m; i++)
    {
        long long int num;
        scanf("%lld", &num);
 
        answer.push_back(num);
    }
 
    for (int i = 0; i < m; i++)
    {
        //        counted = 0;
        lPos = rPos = -1;
 
        if (n - 1 > 0
            && answer[i] > target[n - 1] || answer[i] < target[0])
        {
            printf("0 ");
            continue;
        }
 
        else
        {
//            binarySearch(0, n - 1, answer[i]);
            
            lPos = lower_bound(n, answer[i]);
            rPos = upper_bound(n, answer[i]);
 
            if (lPos == -1 && rPos == -1)
                printf("0 ");
 
            else printf("%d ", rPos - lPos);
 
        }
    }
}

 

느낀점

 

이분 탐색은 매우 빠른 탐색 방법인 줄 알았는데, 최악의 경우에는 결국 다를 게 없다는 점을 배웠다. 그리고, 탐색해서 특정 지점을 찾는 건 빠를지 몰라도, 그 특정 지점이 범위일 때에는 불필요한 연산이 늘어날 수 있다는 것도 알았다. 생각해보면 lower와 upper_bound를 만드는 것은, 결국 이분탐색을 왼쪽 따로 오른쪽 따로 나눠서 하는 것과 크게 다를 바가 없음에도 더 빠르다는 게 신기하게 느껴질 따름이다.

놀라운 것은 STL에 이미 구현되어 있는 lower, upper_bound가 있다는 점이다. (...)