182. 정렬된 배열에서 특정 수의 개수 구하기

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

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

• 입력조건

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

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

• 출력 조건

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

1. Python

이진탐색 구현

#정렬된 수열에서 값이 x인 원소의 개수를 세는 메서드
def count_by_value(array, x):
  n = len(array)
  #첫번째 등장
  a = first(array, x, 0, n - 1)
  if a == None:
    return 0
  #마지막 등장
  b = last(array, x, 0, n - 1)
  return b - a + 1

#처음 위치를 찾는 이진 탐색 메서드
def first(array, target, start, end):
  if start > end:
    return None
  mid = (start + end) // 2
  #해당 값을 가지는 원소 중에서 가장 왼쪽에 있는 경우에만 반환
  if (mid == 0 or target > array[mid - 1]) and array[mid] == target:
    return mid
  elif array[mid] > target:
    return first(array, target, start, mid - 1)
  else:
    return first(array, target, mid + 1, end)

#마지막 위치를 찾는 이진 탐색 메서드
def last(array, target,  start, end):
  if start > end:
    return None
  mid = (start + end )// 2
  #해당 값을 가지는 원소 중에서 가장 오른쪽에 있는 경우에만 인덱스 반환
  if (mid == n - 1 or target < array[mid + 1]) and array[mid] == target:
    return mid
  elif array[mid] > target:
    return last(array, target, start, mid - 1)
  else:
    return last(array, target, mid + 1, end)

n, x = map(int, input().split())
array = list(map(int, input().split()))

count = count_by_value(array, x)
if count == 0:
  print(-1)
else:
  print(count)

bisect 라이브러리

from bisect import bisect_left, bisect_right

#값이 [left_value, right_value]인 데이트의 개수를 반환
def count_by_range(array, left_value, right_value):
  right_index = bisect_right(array, right_value) #한칸 다음 인덱스 반환
  left_index = bisect_left(array, left_value)
  return right_index - left_index

n, x = map(int, input().split())
array = list(map(int, input().split()))

count = count_by_range(array, x, x)
if count == 0:
  print(-1)
else:
  print(count)

2. C++

#include <bits/stdc++.h>

using namespace std;

// 값이 [left_value, right_value]인 데이터의 개수를 반환하는 함수
int countByRange(vector<int>& v, int leftValue, int rightValue) {
    vector<int>::iterator rightIndex = upper_bound(v.begin(), v.end(), rightValue);
    vector<int>::iterator leftIndex = lower_bound(v.begin(), v.end(), leftValue);
    return rightIndex - leftIndex;
}

int n, x;
vector<int> v;

int main() {
    // 데이터의 개수 N, 찾고자 하는 값 x 입력받기
    cin >> n >> x;

    // 전체 데이터 입력 받기
    for (int i = 0; i < n; i++) {
        int temp;
        cin >> temp;
        v.push_back(temp);
    }

    // 값이 [x, x] 범위에 있는 데이터의 개수 계산
    int cnt = countByRange(v, x, x);

    // 값이 x인 원소가 존재하지 않는다면
    if (cnt == 0) {
        cout << -1 << '\n';
    }
    //  값이 x인 원소가 존재한다면
    else {
        cout << cnt << '\n';
    }
}