[BOJ 백준] 20551번 Sort 마스터 배지훈의 후계자

문제

BOJ 20551 : https://www.acmicpc.net/problem/20551

20551번: Sort 마스터 배지훈의 후계자

접근

 오름차순으로 정렬된 배열 arr에서 M개의 임의의 정수들을 찾는 문제이다. arr의 최대 크기는 2×10^5이므로 이분 탐색을 통해 찾아주면 된다. 이때 주의해야 할 점은 배열 안에 중복되는 값이 존재할 수 있고, 우리는 찾아야 하는 임의의 정수 d가 가장 먼저 등장하는 위치를 찾아야 하므로 이분 탐색을 Lower bound로 구현해야 한다는 것을 잊지 말자.

 여기서 내 코드처럼 Lower bound를 직접 구현해도 되지만 값을 vector에 담아 STL의 lower_bound()를 사용하는 간편한 방법도 있다.

lower_bound( v.begin(), v.end(), value);

 

 번외 - 시간 초과의 원인

 만약 본인이 이분 탐색을 제대로 구현했음에도 자꾸 시간 초과가 난다면 입출력에 관해 확인해 봐야 한다.

먼저, C++의 <iostream>의 표준입출력은 생각보다 엄청나게 느리다. 따라서 iostream을 통해 입출력을 하고 싶다면 아래의 코드를 추가해주면 된다.

ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

 ios_base::sync_with_stdio(false); 로 C 표준 입출력과의 동기화를 하지 않도록 설정하여 속도를 올려주고, cin.tie(0); cout.tie(0); 이 코드를 통해 스트림을 untie 시켜서 자동으로 입출력 버퍼를 비우지 않도록 설정하기 때문에 속도를 훨씬 향상할 수 있다. 또한 endl 대신 개행문자(\n)를 사용하도록 하자. endl은 개행을 수행함과 동시에 매번 출력 버퍼를 비워주기 때문에 사용하면 코드가 상당히 느려진다. 내 코드의 endl의 경우 #define을 통해 endl을 개행문자 '\n'으로 치환해주는 매크로 상수임을 알 수 있다. 즉, 사실상 개행문자(\n)인 셈이다. 

 다른 방법으로는 <stdio.h>의 표준 입출력인 printf, scanf를 이용하면 된다.

코드

#include <iostream>
#include <algorithm>
#include <set>

#define endl "\n"

using namespace std;

int n, m, t, arr[200005];
set<int> s;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        s.insert(arr[i]);
    }
    sort(arr, arr + n);
    for (int i = 0; i < m; i++) {
        cin >> t;
        if (s.find(t) == s.end()) {
            cout << -1 << endl;
            continue;
        }
        int left = 0, right = n;
        while (right - left > 0) {
            int mid = (left + right) / 2;
            if (arr[mid] < t)
                left = mid + 1;
            else 
                right = mid;
        }
        cout << right << endl;
    }
    return 0;
}

 

깃 허브 주소 : https://github.com/algoribi/algorithm-study