[코딩테스트 스터디/C++] Zoho인터뷰 정렬된배열에서특정수의개수구하기

1.문제

N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있다. 이때 이 수열에서 x가 등장하는 횟수를 계산하시오. 단, 이 문제는 시간 복잡도 O(logN)으로 알고리즘을 설계하시오. 수열의 원소 중에서 값이 x인 원소가 없다면 -1을 출력한다.

2. 풀이 전 계획과 생각

• 이진 탐색 사용

3. 풀이

#include<iostream>
#include<vector>
#include<algorithm> 
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() {
    // 입력
    cin >> n >> x;

    // 입력
    for (int i = 0; i < n; i++) {
        int temp; cin >> temp;
        v.push_back(temp);
    }

    // 이진탐색  
    int ans = countByRange(v, x, x);

    // 답 출력  
    if (ans == 0) cout << -1;  
    else cout << ans;  
}

upper_bound, lower_bound 모두 이진탐색 기반의 탐색 방법이라 정렬된 배열이나 벡터에 사용이 가능하다. 반환형은 Iterator 이다. 이진탐색이라 시간복잡도 조건을 만족할 수 있다.

upper_bound는 찾으려는 key 값을 초과하는 숫자가 배열 몇 번째에서 처음 등장하는지 찾을 수 있다.

lower_bound는 찾으려는 key 값보다 같거나 큰 숫자가 배열 몇 번째에서 처음 등장하는지 찾을 수 있다.

4. 풀이하면서 고민했던 점

• 처음에 이진탐색으로 x원소를 찾고 그 앞, 뒤 원소를 순회하면서 찾으려고 했는데 생각해보니 최악의 경우 시간복잡도가 O(N)이라서 실패함

5. 문제를 풀고 알게된 개념 및 소감

• upper_bound, lower_bound에 대해 알게되었다.