[HackerRank] Climbing the Leaderboard

해당 문제는 음수값으로 정렬하여 높은 점수를 정렬 시켜서 문제를 풀었습니다.

초기에 입력받을때 set자료구조를 활용하여 중복 값을 제거 시킨뒤, 플레이어를 한명씩 추가할때마다 bisect_left를 사용하여 플레이어의 rank위치 인덱스를 가져온뒤, 같은 점수가 있는 플레이어는 ranked 배열에 삽입하지않고 무시한다. 그렇지 않다면 rank배열에 찾은 인덱스에 값을 추가하면 된다. 이렇게 하면 이분 탐색으로 빠르게 문제를 해결 할 수 있다. 시간복잡도는 log(mlogn) 으로 m은 player의개수 logn은 rank의 개수이다.

import sys
from bisect import bisect_left

input = sys.stdin.readline

N = int(input())
temp = set(map(int, input().split()))

ranked = []
for i in temp:
    idx = bisect_left(ranked, -i)
    ranked.insert(idx, -i)

M = int(input())
player = list(map(int, input().split()))
result = []
for p in player:
    idx = bisect_left(ranked, -p)
    result.append(idx+1)
    if idx < len(ranked) and ranked[idx] == -p:
        continue

    ranked.insert(idx, -p)

for num in result:
    print(num)