성적 평가

과정 설계

Heap

이 문제에서의 관건은 score 리스트에서 어떻게 순위를 매길 것인가? 이다.

직관적으로 접근하면 이중 반복문을 통해 간단히 구현할 수 있지만
입력 제한이 10^5 이므로 O(N^2)로 풀면 시간 초과가 발생할 것이다.

따라서 힙 자료구조를 이용했다.
랭크 리스트를 초기화 해준후
최대힙을 이용해서 하나씩 빼주며 해당 점수에 해당하는 인덱스에 순위를 매겼다.

코드

import sys
import heapq as h
input = sys.stdin.readline

def score_to_rank(mh):
    rank = [0]*n
    now_rank = 1
    save_rank = 0
    save_sc = 0
    while mh:
        now = h.heappop(mh)
        if now[0] == save_sc:
            rank[now[1]] = save_rank
        else:
            rank[now[1]] = now_rank
            save_rank = now_rank
            save_sc = now[0]
        now_rank += 1
    return rank

n = int(input())
score = []
rank = []
max_heap = []
for i in range(3):
    score.append(list(map(int,input().split())))
score.append([0]*n)
for i in range(n):
    score[-1][i] += score[0][i]+score[1][i]+score[2][i]
for i in range(4):
    temp = []
    for j in range(n):
        h.heappush(temp,(-score[i][j],j))
    max_heap.append(temp)
for i in range(4):
    mh = max_heap[i]
    rank.append(score_to_rank(mh))
for i in range(4):
    print(*rank[i])