프로그래머스 lv0 등수매기기

1. 개요

• https://school.programmers.co.kr/learn/courses/30/lessons/120882

2. 풀이

```python def solution(score): # score를 합기준으로 내림차순으로 정렬한다. links = sorted(score, key=lambda link: sum(link), reverse=True) ranks, curRank, last = dict(), 1, 0

# score 배열의 원소에 해당하는 랭크를 저장할 ranks 선언
ranks[tuple(links[0])] = curRank

# links들중 하나씩 검사해서 이전 link합과 현재의 합이 같으면 랭크를 유지
# 다르면 링크의 인덱스를 활용해 랭크를 갱신한다.
for i in range(1, len(links)):
    if sum(links[i-1]) != sum(links[i]):
        curRank = i+1
    ranks[tuple(links[i])] = curRank

# 이제 ranks 사전을 통해 score를 모두 rank로 변환할수 있다.
return [ranks[tuple(s)] for s in score]

def solution(score): # 점수의합을 구해서 내림차순으로 정렬한다. a = sorted([sum(s) for s in score], reverse=True)

# 합에 대한 인덱스를 구할수 있는데
# 가장 낮은 인덱스를 구할수 있다. (O(N*N)) 그런데 score가 엄청 많으면 어떻게 할까
return [a.index(sum(s))+1 for s in score]

이진탐색을 통한 풀이

from bisect import bisect_right

def solution(score): # 이번에는 점수의합을 구해서 오름차순으로 정렬한다. a = sorted([sum(s) for s in score]) N = len(score)

# 이진탐색을 통해 upper_bound를 구한후 이값을 N에서 빼고 +1을 더하면 rank를 구할수 있다.
# 이러면 score의 갯수가 클때 빠르게 랭크를 구할수 있다. (O(NlogN))
return [N-bisect_right(a, sum(s))+1 for s in score]