[C++] 정렬된 배열에서 특정 수의 개수 구하기

1. 문제

N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있습니다. 이때 이 수열에서 x가 등장하는 횟수를 계산하세요. 예를 들어 수열 {1, 1, 2, 2, 2, 2, 3}이 있을 때 x = 2라면, 현재 수열에서 값이 2인 원소가 4개이므로 4를 출력합니다.
단, 이 문제는 시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 '시간 초과' 판정을 받습니다.

2. 입력 조건

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

3. 출력 조건

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

4. 풀이

• 정렬된 배열이기 때문에 시작과 끝을 찾아주면 된다.
• 시작은 lower_bound로 끝은 upper_bound로 찾아준다.

  lower_bound - 참고 블로그
  lower_bound - cpp reference

• 마지막 인덱스에서 시작 인덱스를 뺀 값을 출력한다.
• 값이 0일 경우 -1을 출력한다.

5. 처음 코드와 달라진 점

• -1 처리를 안 해줘서 수정해주었다.

6. 코드

#include <iostream>
#include <vector>

using namespace std;

int n, target;
vector<int> arr;

int countByRange(vector<int> &arr, int leftValue, int rightValue) {
  vector<int>::iterator rightIndex = upper_bound(arr.begin(), arr.end(), rightValue);
  vector<int>::iterator leftIndex = lower_bound(arr.begin(), arr.end(), leftValue);

  return rightIndex - leftIndex;
}

int main() {
  cin >> n >> target;
  
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    arr.push_back(x);
  }

  int answer = countByRange(arr, target, target);
  if (answer == 0) cout<< -1;
  else cout<<answer;
}