[2517번] 달리기

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 세그먼트 트리 :: http://www.crocus.co.kr/648

이 문제의 핵심은 다음과 같다.

1. 값이 10억까지 들어올 수 있지만 n제한이 50만 이하이다. 따라서 좌표 압축이 가능하다.

2. 좌표압축이 이루어 진다면 세그먼트 트리를 이용하여 문제를 해결 할 수 있다.

3. 세그먼트 트리를 이용하는 법은 다음과 같다.

현재 입력값보다 먼저 들어온 값들 중 자신보다 큰 값이 있으면 

그 개수를 count 해주고, 없다면 0 + 1(자신)을 해준다는 원리로 진행한다.

이 문제를 풀때 필자는 다음과 같은 생각을 몇가지 해보았다.

현재 들어온 값이 맵의 end() -1에 존재하면 끝에 위치하는거니 1등이 될 가능성이 있는 것이고, 그게 아닌 모든 값들은 맵에서 몇번째에 위치하는지 order를 구해주면 된다고 생각했다.

그런데 order 구하는 방법이 logN에 끝날 줄 알았는데 그 방법을 찾지 못하였다.

예를들어 vector에서는 lower_bound() - V.begin()을 하면 인덱스가 나타나지만 map은 균형 이진 트리라 인덱스 개념이 없다보니 안되는 것 같았다.

틀린 코드는 다음과 같다.

이때 아래 distance 자체가 O(n)에 끝나는 방식이고, lower_bound 자체는 map에서 제공하지만, 인덱스를 반환해줄 방법이 없다.

시간초과(TLE) 코드

#include <iostream>
#include <cstdio>
#include <map>
 
using namespace std;
 
map<int, int> mp;
 
int main()
{
    int n;
    scanf("%d", &n);
 
    for (int i = 1; i <= n; i++)
    {
        int val;
        scanf("%d", &val);
        mp[val] = i;
 
        auto pos = mp.lower_bound(val);
        if (pos == --mp.end())
            printf("1\n");
 
        else
            printf("%d\n", i - distance(mp.begin(), pos));
    }
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
 
using namespace std;
 
typedef pair<int, int> pii;
 
bool comp(const pii &a, const pii &b)
{
    return a.second < b.second;
}
 
void update(vector<int> &tree, int node, int start, int end, int idx)
{
    if (!(start <= idx && idx <= end))
        return ;
 
    tree[node] += 1;
 
    if (start != end)
    {
        int mid = (start + end) / 2;
        update(tree, node * 2, start, mid, idx);
        update(tree, node * 2 + 1, mid + 1, end, idx);
    }
 
}
int query(vector<int> &tree, int node, int start, int end, int left, int right)
{
    if (start > right || end < left)
        return 0;
    
    if (left <= start && end <= right)
        return tree[node];
 
    int mid = (start + end) / 2;
 
    return query(tree, node * 2, start, mid, left, right) + query(tree, node * 2 + 1, mid + 1, end, left, right);
}
 
int main()
{
    int n;
    scanf("%d", &n);
 
    int h = (int)ceil(log2(500000));
    int tree_size = 1 << (1 + h);
 
    vector<pii> arr;
    vector<int> tree(tree_size);
 
    for (int i = 0; i < n; i++)
    {
        int val;
        scanf("%d", &val);
        arr.push_back({ val, i });
    }
 
    sort(arr.begin(), arr.end());
 
    // 좌표 압축
    for (int i = 0; i < n; i++)
        arr[i].first = i;
 
    sort(arr.begin(), arr.end(), comp);
 
    for (int i = 0; i < n; i++)
    {
        int ans = i - query(tree, 1, 0, 500000, 0, arr[i].first) + 1;
        printf("%d\n", ans);
 
        update(tree, 1, 0, 500000, arr[i].first);
    }
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>