Climbing the Leaderboard

문제

https://www.hackerrank.com/challenges/climbing-the-leaderboard/problem?h_r=profile

Climbing the Leaderboard | HackerRank

 

풀이

시간복잡도를 고려했을때 단순 정렬을 하면 시간제한이 걸리므로 이분탐색으로 찾아 해결하였다.

 

코드

// Complete the climbingLeaderboard function below.
vector<int> climbingLeaderboard(vector<int> scores, vector<int> alice) {
        
    vector<int> rank;
    vector<int> aliceRanks;
    
    rank.push_back(1);
    int beforeScore = scores[0];
    for(int i=1; i<scores.size(); i++){
        if(beforeScore == scores[i]){
            rank.push_back(rank[i-1]);
        }else{
            rank.push_back(rank[i-1]+1);
        }
        beforeScore = scores[i];
    }
    
    

    for(int i=0; i<alice.size(); i++){
        int aliceScore = alice[i];
        int start = 0, end = scores.size()-1;
        
        int aliceRank = -1;
        
        int mid = -1;
        while(end>=start){
             mid = (start+end)/2;
            if(scores[mid] == aliceScore){
                break;
            }
            else if(scores[mid]<aliceScore){
                end = mid-1;
            }else{
                start = mid+1;
            }
        }
        
        aliceRank = (aliceScore>=scores[mid])? rank[mid] : rank[mid]+1;
        aliceRanks.push_back(aliceRank);
        
    }

    
    return aliceRanks;
    
}