백준 10816번: 숫자 카드 2

문제 링크 : https://www.acmicpc.net/problem/10816

참고한 블로그 : https://yhwan.tistory.com/10

이분 탐색은 정렬된 배열 또는 수열에서 특정한 값 num을 찾을 때 중간값을 이용해 탐색 범위를 줄여나가면서 빠르게 탐색하는 것이다.

이번 문제는 이분 탐색을 이용하되, num이 존재하는지를 찾는 것이 아니라 배열 안에 n이 몇 개가 들어있는지 개수를 찾아야 하는 문제였다. 어떻게 풀 지 감이 잡히지 않아서 검색해서 방법만 참고하여 코드를 작성했다.

배열과 num이 주어질 때, num이 시작하는 인덱스와 끝나는 인덱스를 구해서 (끝 - 시작)을 하면 전체 num의 개수를 구할 수 있다는 것이다. 시작 위치와 끝 위치를 구하는 함수는 등호 하나 차이로 달라지게 됐다.

// n = 전역변수
int startLoc(int num){
    int start = 0, end = n - 1, mid;
    while(start < end){
        mid = (start + end) / 2;
        if(num <= a[mid])
            end = mid;
        else
            start = mid + 1;
    }
    return end;
}

int endLoc(int num){
    int start = 0, end = n - 1, mid;
    while(start < end){
        mid = (start + end) / 2;
        if(num < a[mid])
            end = mid;
        else
            start = mid + 1;
    }
    return end;
}

이분 탐색의 기본적인 코드 그대로 가면서 while문 안의 if문 조건에서 등호 하나가 들어가느냐 안들어가느냐로 결과가 달라지다니.. 문제에서 주어진 기본 예제로 두 함수를 돌려보면 어떤 차이로 값이 달라지는지 금방 알 수 있다.

<작성한 코드>

#include <iostream>
#include <algorithm>
using namespace std;

int a[500001];
int n, m;

int startLoc(int num){
    int start = 0, end = n - 1, mid;
    while(start < end){
        mid = (start + end) / 2;
        if(num <= a[mid])
            end = mid;
        else
            start = mid + 1;
    }
    return end;
}

int endLoc(int num){
    int start = 0, end = n - 1, mid;
    while(start < end){
        mid = (start + end) / 2;
        if(num < a[mid])
            end = mid;
        else
            start = mid + 1;
    }
    return end;
}

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    
    sort(a, a + n);
    
    scanf("%d", &m);
    for(int i = 0; i < m; i++){
        int temp, st, en;
        scanf("%d", &temp);
        st = startLoc(temp);
        en = endLoc(temp);
        if(en == n - 1 && a[en] == temp)
            en++;
        
        printf("%d ", en - st);
    }
}