[Python] Hackerrank. Climbing the Leaderboard (Medium)

https://www.hackerrank.com/challenges/climbing-the-leaderboard/problem

Climbing the Leaderboard | HackerRank

전체 scoreboard 값이 주어져 있고, alice의 score가 주어지면 해당 score는 전체 scoreboard에서 몇 등인지를 표시하는 문제. 해커랭크에서 이 문제는 'Implementation'으로 분류돼 있다.

 

처음 봤을 땐 단순히 'alice의 매 score를 scoreboard에서 binary search해서 풀면 되겠다' 생각했는데, time limit에 걸렸다. 아니 이분탐색을 해도 효율성에 걸리는 문제가 있나? 싶었다. 여러 가지 변형을 시도해봤지만 test case 6, 7, 8, 9 네 개를 통과 못해서, 접근방법에 문제가 있나 싶어 결국 discussion을 확인했다.

 

implementation으로 분류된 이유가 있었다. 문제에 주어진 제한조건을 보면 score는 내림차순, alice의 값은 오름차순이다.

 

그 말인즉,

alice 맨 앞 값에서부터 iteration을 돌 때,

score 맨 뒤에서부터 index로 alice와 값을 비교하고, score[idx] > alice 일 때의 idx값을 활용해서 풀어야 한다.

 

alice가 오름차순으로 주어졌기 때문에, 한 번 지나간 score[idx]는 다시 검사할 필요가 없다는 게 포인트였다. 이렇게 되면 매번 탐색할 때마다 다음에 탐색해야 할 범위가 줄어들기 때문에, 매번 처음부터 시작해서 이분탐색으로 값을 찾는 것보다 빨라질 수 있다는 것.