10주차(이진탐색) - [C++]백준10816 숫자 카드 2

20 May 2022 in Study on Algorithm

백준10816 숫자 카드 링크

문제

예제 입력

---

코드

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

vector<int> arr;
int n, m;

// key 값 초과인 위치
int UpperBound(int key) {
    int mid = 0;
    int st = 0;
    int end = arr.size();
    while (st < end) {
        mid = (st + end) / 2;

        if (arr[mid] > key) {
            end = mid;
        }
        else {
            st = mid + 1;
        }
    }
    return st;
}

// key 값 이상인 위치
int LowerBound(int key) {
    int mid = 0;
    int st = 0;
    int end = arr.size();
    while (st < end) {
        mid = (st + end) / 2;

        if (arr[mid] >= key) {
            end = mid;
        }
        else {
            st = mid + 1;
        }
    }
    return st;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        arr.push_back(a);
    }
    sort(arr.begin(), arr.end());

    cin >> m;
    for (int i = 0; i < m; i++) {
        int key;
        cin >> key;
        //auto l = lower_bound(arr.begin(), arr.end(), key);
        //auto r = upper_bound(arr.begin(), arr.end(), key);
        cout << UpperBound(key) - LowerBound(key) << ' ';
    }
}

설명

이 문제는 이진 탐색의 개념을 응용하여 중복된 값의 갯수까지 구하는 것입니다. C++ STL(표준 템플릿 라이브러리)에서 vector를 사용하여 구현했습니다. 키값을 받아 배열에 해당 값이 몇개가 있는지 확인하기 위해서 키값의 이상과 초과인 위치를 찾아서 두 개의 위치값을 빼면 확인이 가능합니다.

<algorithm>
-sort(시작, 끝, 비교함수) : 배열의 크기만큼 정렬

<vector>
-vector<자료형> 변수명; : 배열 자료구조 사용

---

결과