[Hackerrank] 23. Lower-Bound STL

23. Lower-Bound STL

[ 난이도: Easy | 분야: STL ]

1. 과제

과제 설명

정렬된 순서대로 N개의 정수가 있다. 또한, Q 쿼리가 있다.

각 쿼리에는, 정수가 있고 그 정수가 배열 안에 있는지 알려주면 된다.

만약 있다고 하면, 그 정수가 있는 위치를 반환하고 만약 없다고 하면, 주어진 정수보다 크지만, 큰 수들 중에서 제일 작은 정수의 위치를 반환하라.

Lower bound는 정렬된 벡터를 사용하는 함수다.

 

입력 형식

첫 번째 줄에는 정수의 개수인 N을 포함하고 있다.

다음 줄에는 정렬된 순으로 N 개의 정수가 있다.

다음 줄에는 쿼리의 개수인 Q를 포함하고 있다.

그다음 Q 개의 줄이 단일 정수 Y를 포함하고 있다.

요약: 만약 같은 수가 여러 번 나온다면, 첫 번째 위치를 반환한다. 또한, 입력은 각 쿼리에 대한 답을 주도록 설계되어 있다.

 

제약 사항

N은 1보다 크거나 같고 10^5보다 작거나 같다.

X_i는 1보다 크거나 같고 10^9보다 작거나 같다.(여기서 X_i는 배열에서 i번째 요소를 의미한다.)

Q는 1보다 크거나 같고 10^5보다 작거나 같다.

Y는 1보다 크거나 같고 10^9보다 작거나 같다.

 

출력 형식

각 쿼리는 숫자가 있다면 Yes를 출력하고 공백으로 구분하여 배열에서의 위치를 출력해라.

만약 숫자가 없다면 No를 출력하고 다음으로 작은 숫자(주어진 수보다 더 큰)의 배열의 위치(1부터 시작하는)를 출력해라.

각 쿼리를 개별 줄에 표현하라.

 

입력 예시

8
1 1 2 2 6 9 9 15
4
1
4
9
15

 

출력 예시

Yes 1
No 5
Yes 6
Yes 8

 

문제

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


int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    return 0;
}

정답

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


int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    int n = 0;
    cin >> n; // number of integers
    vector<int> v;
    // Push back into vector
    for(int i = 0; i < n; i++) {
        int temp = 0;
        cin >> temp;
        v.push_back(temp);
    }
    int q = 0;
    cin >> q; // number of queries
    // Find the value
    int index = 0;
    int numbers = 0;
    for(int i = 0; i < q; i++) {
        cin >> numbers;
        // If Exist
        if(binary_search(v.begin(),v.end(),numbers)) {
            cout << "Yes" << " ";
        }
        // If Not Exist
        else {
            cout << "No" << " ";
        }
        index = lower_bound(v.begin(), v.end(), numbers) - v.begin() + 1;
        cout << index << endl;
    }
    return 0;
}

 

이번 문제는 find로 존재 여부를 탐색할 경우 테케에 time_out으로 걸리게 된다.

binary_search를 적극 활용하여(오름차순으로 정렬되어 있기 때문) 시간을 단축하는 것이 핵심이다.

 

 

 

 

 

 

©️Hackerrank. All Rights Reserved.