September 24, 2021

문제

N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있습니다. 이때 이 수열에서 x가 등장하는 횟수를 계산하세요. 예를 들어, {1, 1, 2, 2, 2, 2, 3}이 있을 때 x = 2라면, 현재 수열에서 값이 2인 원소가 4개이므로 4를 출력합니다.

단, 이 문제는 시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 시간 초과 판정을 받습니다.

시간 제한

1초

메모리 제한

128MB

입력 조건

첫째 줄에 N과 x가 정수 형태로 공백으로 구분되어 입력됩니다. (1≤N≤1,000,000, -10^9 ≤x≤10^9)

둘째 줄에 N개의 원소가 정수 형태로 공백으로 구분되어 입력됩니다. (-10^9≤x≤10^9)

출력 조건

수열의 원소 중에서 값이 x인 원소의 개수를 출력합니다. 단, 값이 x인 원소가 하나도 없다면 -1을 출력합니다.

풀이

#include <stdio.h>
#include <vector>

using namespace std;

int N, x, lowerIdx, upperIdx;
vector<int> arr;

void lowerBound(int start, int end) {
    int mid = (start + end) / 2;

    if (start > end) return;

    if (arr[mid] == x) {
        lowerIdx = mid;

        lowerBound(start, mid - 1);
    } else if (arr[mid] < x) {
        lowerBound(mid + 1, end);
    } else {
        lowerBound(start, mid - 1);
    }
}

void upperBound(int start, int end) {
    int mid = (start + end) / 2;

    if (start > end) return;

    if (arr[mid] == x) {
        upperIdx = mid + 1;

        upperBound(mid + 1, end);
    } else if (arr[mid] < x) {
        upperBound(mid + 1, end);
    } else {
        upperBound(start, mid - 1);
    }
}

int easyFind() {
    lowerIdx = lower_bound(arr.begin(), arr.end(), x) - arr.begin();
    upperIdx = upper_bound(arr.begin(), arr.end(), x) - arr.begin();

    return upperIdx - lowerIdx;
}

int main() {
    int tmp;

    scanf("%d %d", &N, &x);

    for (int i = 0; i < N; ++i) {
        scanf("%d", &tmp);

        arr.push_back(tmp);
    }

    lowerBound(0, N - 1);
    upperBound(0, N - 1);

    printf("%d %d", upperIdx - lowerIdx, easyFind());

    return 0;
}

이진 탐색을 이용하여 해당 값의 인덱스 시작 값과 끝 + 1 값을 찾는다.