[소프티어 6250번] 성적 평가(HSAT 5회 정기 코딩 인증평가 기출)

import sys

input = sys.stdin.readline

# N명의 인원이 참여하는 스터디
# 3개의 대회, 모든 구성원이 각 대회에 참여
# 참가자는 각 대회에서 0이상 1000이하의 정수인 점수를 얻음
# 한 대회에서 둘 이상의 참가자가 동점이 나오는 경우도 있음

# 각 대회 별로 등수 및 최종 등수를 매김
# 동점인 경우에는 공동 등수, 아닌 경우에는 일반 등수
# 즉, 등수 = 나보다 점수가 높은 사람의 수 +  1

# 각 참가자의 대회별 등수 / 최종 등수 출력
# 입력 최대 범위 : 10^5

n = int(input())

score_list = []
sum_list = [0] * n

for _ in range(3):
    init = list(map(int,input().split()))

    for i, score in enumerate(init):
        sum_list[i] += score
        
    scores = sorted(init,reverse=True)

    score_dict = dict()
    rank = 1
    count = 1

    for i, score in enumerate(scores):
        if i == 0:
            score_dict[score] = count
        else:
            if scores[i-1] == score:
                score_dict[score] = rank
                count += 1
            else:
                rank += count
                score_dict[score] = rank
                count = 1
    for i in range(n):
        print(score_dict[init[i]],end=" ")
    print()

rank, count = 1, 1
sorted_sum_list = sorted(sum_list,reverse=True)
score_dict2 = dict()

for i, score in enumerate(sorted_sum_list):
    if i == 0:
        score_dict2[score] = count
    else:
        if sorted_sum_list[i-1] == score:
            score_dict2[score] = rank
            count += 1
        else:
            rank += count
            score_dict2[score] = rank
            count = 1

for i in range(n):
    print(score_dict2[sum_list[i]],end=" ")

 

이번 문제는 N명이 참가한 3개의 대회에서 각 대회 별 회원의 등수와 최종 등수를 구하는 문제이다.

 

문제 자체는 난이도가 높지 않은데, 조금 까다로웠던 건 등수를 매기는 방식의 SQL의 RANK() 함수와 동일한 방식이라는 것이다. (중복 순위 개수만큼 다음 순위 값을 증가)

 

먼저 입력값의 범위가 최대 10^5 였기 때문에 시간복잡도를 O(N^2)로는 풀면 안되겠다고 생각했고, 시간복잡도를 최소화하기 위해 노력했다.

 

문제풀이 방법은 다음과 같다.

 

1. 먼저 점수들을 오름차순으로 정렬해준다.(O(NlogN))
2. 현재 점수가 이전 점수와 같은 경우에는 등수(rank)는 동일하게 가져가고, 중복 순위의 개수(count)를 +1 해준다.
3. 현재 점수가 이전 점수와 다른 경우에는 등수(rank)를 중복 순위의 개수(count) 만큼 더해준 뒤 등수를 업데이트 한다.
4. 모든 등수는 사전 자료형(score_dict)에 저장하고 오름차순 순서대로 출력한다.