[BOJ 20495 // C++] 수열과 헌팅

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 20495번 문제인 수열과 헌팅이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/20495

20495번: 수열과 헌팅

문제풀이의 아이디어는 간단하다.

주어진 범위 내에서 정해진 수가 있을 수 있는 index의 범위를 구하는 것이므로,

가장 낮은 index가 나올 경우는 구하는 수는 범위에서 최솟값을 갖고 나머지 수들은 범위에서 각각 최댓값을 가지는 경우에 발생할 것이고,

가장 큰 index가 나올 경우는 구하는 수는 범위에서 최댓값을 갖고 나머지 수들은 범위에서 각각 최솟값을 가지는 경우에 발생할 것이다.

 

그러므로 미리 가장 낮은 index끼리 정렬을 해두고, 가장 큰 index끼리 정렬을 해둔 뒤 각 구간의 최댓값 최솟값을 binary search로 각 배열에서 bound를 찾아 문제를 해결할 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <algorithm>
using std::cin;
using std::cout;
using std::sort;

int arrx[500000];
int arry[500000];
int sortarrx[500000];
int sortarry[500000];

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

    int n;
    cin >> n;
    int x, y;
    for (int i = 0;i < n;i++) {
        cin >> x >> y;
        arrx[i] = x-y;
        sortarrx[i] = x-y;
        arry[i] = x+y;
        sortarry[i] = x+y;
    }

    sort(sortarrx, sortarrx + n);
    sort(sortarry, sortarry + n);

    int temp;
    for (int i = 0;i < n;i++) { 
        int left = 0, right = n - 1;
        x = arrx[i];
        y = arry[i];
        while (left <= right) { // 작은 index
            int mid = (left + right) / 2;
            if (sortarry[mid] >= x) {
                right = mid - 1;
            }
            else left = mid + 1;
        }
        cout << left+1 << ' ';
        left = 0, right = n - 1; // 큰 index
        while (left <= right) {
            int mid = (left + right) / 2;
            if (sortarrx[mid] <= y) {
                left = mid + 1;
            }
            else right = mid - 1;
        }
        cout << right+1 << '\n';
    }

    return 0;
}