[BOJ] 2517번 : 달리기

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

2517번: 달리기

2012년도 정올 고등부 2번 문제다. segment tree와 좌표압축을 사용하면 된다.

 

실력을 기준으로 segment tree를 만들면 특정 실력의 선수를 확인할 때 O(logN)만에 최대 등수를 확인할 수 있다는 아이디어를 얻을 수 있다. 여기서 중요한 점은 앞에서부터 차례로 update를 해 주고 query를 처리하여서 i번째 선수까지만 tree에 반영이 될 수 있도록 하는 것이다.

 

이런 아이디어의 문제점은 실력이 10억 이하의 자연수로 제시된다는 점이다. 이 경우 실력 값을 기준으로 tree를 구축하면 space complexity의 조건을 만족하지 못한다. 따라서 n의 최대값이 50만이라는 점을 이용하여 좌표압축을 해 주어야 한다. 좌표압축을 시행하면 실력이 최대 50만으로 나타내어지므로 tree에 손쉽게 넣을 수 있다. 좌표압축은 다음과 같이 수행할 수 있다.

 

void coordCompress(int n) {
    vector<int> tempVec;
    map<int,int> contAbility;
    
    tempVec.resize(player.size());
    copy(player.begin(),player.end(),tempVec.begin());
    sort(tempVec.begin(),tempVec.end());
    
    int temp=1;
    contAbility.insert(make_pair(tempVec[0],1));
    for(int i =1; i<n; i++) {
        if(tempVec[i]>tempVec[i-1]) temp++;
        contAbility.insert(make_pair(tempVec[i],temp));
    }
    for(int i =0; i<n; i++)    player[i]=contAbility[player[i]];
}