[백준] 10816 숫자 카드2

March 20, 2021 ( last updated : March 20, 2021 )
이분탐색 알고리즘 algorithm

https://github.com/sneakstarberry/

Abstract

[백준] 10816번 숫자 카드2

[백준] 10816번 숫자 카드2

백준 10816번

알고리즘 유형

풀이 방법

문제를 보면 결국 구해야할 것은 타겟 값의 갯 수이다. 예제의 첫번째 타겟 값 10을 통해서 방법을 생각해보자.

타겟 값: 10
배열: 6 3 2 10 10 10 -10 -10 7 3

먼저 배열을 정렬한다.

정렬된 배열: -10, -10, 2, 3, 3, 6, 7, 10, 10, 10

정렬된 배열에서 첫번째 타겟 값을 찾고 타겟 값보다 한 단계 낮은 값의 인덱스 값을 찾는 다. 그리고 타겟 값보다 큰 값이 나오는 인덱스 값을 찾는다. 이후 큰 값의 인덱스에서 작은 값의 인덱스를 빼면 타겟 값의 갯 수가 나온다.

하지만 일반적인 탐색으로 해당 방법을 실행하면 시간초과가 나온다. 시간초과가 나오지 않을 려면 이분탐색을 통해 탐색 시간을 줄여야한다.

c++에서 이를 함수로 구현한 것이 lower_bound이다. 해당 함수를 통해서 쉽게 문제를 풀 수 있었다.

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

int N, M;
vector<int> CARD, T;

void input()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        int tmp;
        cin >> tmp;
        CARD.push_back(tmp);
    }
    cin >> M;
    for (int i = 0; i < M; i++)
    {
        int tmp;
        cin >> tmp;
        T.push_back(tmp);
    }
}

int main(){
    input();
    vector<int> v;
    vector<int>::iterator low;
    vector<int>::iterator upper;

    sort(CARD.begin(), CARD.end());


    for (int i = 0; i < M; i++) {
        low = lower_bound(CARD.begin(), CARD.end(), T[i]);
        upper = lower_bound(CARD.begin(), CARD.end(), T[i] + 1);

        cout << upper - low << ' ';
    }
}

Originally published March 20, 2021
Latest update March 20, 2021

Related posts :

{# #}