코드업(codeup) 2633 : Lower Bound C언어

▶문제 : Lower Bound (codeup.kr)

Lower Bound

 

▶코드 작성

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int n, k, i, ct, right, left;
    int *arr;

    scanf("%d %d", &n, &k);

    arr = (int *)malloc(sizeof(int) * n);

    for (i = 0; i < n; i++)
    {
        scanf("%d", &arr[i]);
    }

    if (k > arr[n - 1])//모든 숫자가 k보다 클 때
    {
        printf("%d", n + 1);
        return 1;
    }

    left = 0;
    right = n - 1;
    while (left <= right)
    {
        ct = (left + right) / 2;//배열 중앙값
        if (k < arr[ct]) right = ct - 1;//배열 오른쪽(중앙값보다 큼)에 있을 때
        else if (k > arr[ct]) left = ct + 1;//배열 왼쪽(중앙값보다 작음)에 있을 때
        else if (k == arr[ct]) break;
    }

    if (k > arr[ct])//k값이 배열에 없을 때
    {
        while (k < arr[ct++]);
    }
    else
    {
        while (ct > 0)
        {
            if (k > arr[ct - 1]) break;//k값인 배열중 맨 앞 자리 찾기
            else ct--;
        }
    }

    printf("%d", ct + 1);

    free(arr);

    return 0;
}

 

▶해석

배열이 오름차순이므로 이분 탐색을 사용함. 중앙값을 이용하여 k값을 찾아냄.