[C++] 백준 2517 : 달리기

1. 문제 출처

https://www.acmicpc.net/problem/2517

2517번: 달리기

 

2. 문제 접근

https://www.acmicpc.net/problem/10090

10090번: Counting Inversions

 

 

 

 

위의 문제와 상당히 유사하다고 느껴진 문제이다. 먼저 주어진 문제에서 각 선수들은 최대 50만 명이라고 주어진다. 또한 각 선수마다 능력치가 주어지는데 그 능력치는 최대 10억이라고 주어진다. 각 선수마다 능력치는 중복이 되지 않으므로, 이 10억까지의 능력치를 다시 번호를 매길 필요가 있다. 그 이유는 세그먼트 트리의 크기를 줄이기 위해서다.

 

 

 

 

 

선수들을 능력치가 낮은 것부터 점점 높아지게 정렬을 한다. 그리고 각 선수들의 능력치를 0부터 n-1까지 순서대로 다시 부여한다. 이렇게 해도 "나보다 낮은 선수들은 여전히 낮기"때문에 그 능력치의 크기만 줄었을 뿐 해결하는 데에 문제가 생기지 않는다.

 

 

 

 

 

이후 세그먼트 트리를 생성하고, query함수는 내 앞에 구간의 수를 반환하도록 설정한다.

 

 

 

query함수의 역할: 나 보다 앞에 있는 선수들 중 나보다 큰 능력치를 가진 사람을 반환

 

 

 

 

위의 역할을 수행하기 위해서 트리에 값을 삽입(update)할 때는 능력치가 큰 사람 순으로 업데이트 해야한다. 그렇게 하지 않으면 나보다 앞에 있는 선수들 중 나보다 작은 능력치를 가진 사람들의 수도 반환이 되어 버린다.

 

 

 

 

 

update함수는 기존 세그먼트 트리와 동일하게 현재 내 index위치에 +1을 해주고 트리를 업데이트 한다.

결과적으로, 나보다 앞에 있는 사람이 1명 있다면 내 등수는 2등이 되는 것이다. 따라서 정답으로는 query로 반환받은 값에 1을 더한 것을 출력해주면 된다.

 

 

 

 

 

 

 

3. 코드

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

int n;
vector<pair<int, int>> arr;
vector<int> tree;

// node가 담고 있는 구간: [left, right]
// 내가 변경하고자 하고 싶은 구간: [start, end]
void updateTree(int node, int left, int right, int index, int diff) {
    if (index < left || right < index) return;

    tree[node] += diff;

    if (left != right) {
        int mid = (left + right) / 2;
        updateTree(node * 2, left, mid, index, diff);
        updateTree(node * 2 + 1, mid + 1, right, index, diff);
    }
}

// 내 앞에 나보다 큰 사람들이 몇명이나 있나?
int queryTree(int node, int left, int right, int start, int end) {
    if (end < left || right < start) return 0;
    if (start <= left && right <= end) return tree[node];
    int mid = (left + right) / 2;
    return queryTree(node * 2, left, mid, start, end) + queryTree(node * 2 + 1, mid + 1, right, start, end);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n;
    arr.resize(n);

    // first: 선수들의 기본 index
    // second: 선수들의 실력 정보
    for (int i = 0; i < n; ++i) {
        arr[i].first = i;
        cin >> arr[i].second;
    }

    // 모든 선수들의 실력을 낮은 순서대로 정렬
    sort(arr.begin(), arr.end(), [](const auto &a, const auto &b) {
        return a.second < b.second;
    });

    // Renumbering
    for (int i = 0; i < n; ++i)
        arr[i].second = i;

    int treeHeight = ceil(log2(n));
    int treeSize = 1 << (treeHeight + 1);
    tree.resize(treeSize, 0);

    vector<pair<int, int>> result(n);

    // 능력치가 큰 사람부터 삽입합니다.
    for (int i = n - 1; i >= 0; --i) {
        result[i].first = arr[i].first;
        result[i].second = queryTree(1, 0, n - 1, 0, arr[i].first - 1) + 1;
        updateTree(1, 0, n - 1, arr[i].first, 1);
    }

    sort(result.begin(), result.end());
    for (auto e : result) {
        cout << e.second << "\n";
    }

    return 0;
}