[파이썬] 현대자동차 Softeer :: 성적평가 풀이

 

Softeer

 

1. 문제

현주는 N명의 인원이 참여하는 프로그래밍 스터디 그룹을 이끌고 있다.

현주는 스터디를 위해 대회를 세 개 개최하였고, 모든 구성원이 각 대회에 참여하였다. 참가자는 각 대회에서 0 이상 1,000 이하의 정수인 점수를 얻는다. 한 대회에서 둘 이상의 참가자가 동점이 나오는 경우도 있을 수 있다.

현주는 각 대회별 등수 및 최종 등수를 매기고 싶다. 등수는 가장 점수가 높은 사람부터 1등, 2등, ···, N등의 순서대로 붙는다. 만일 동점이 있을 경우 가능한 높은 (등수의 수가 작은) 등수를 부여한다. 즉, 점수가 내림차순으로 10,7,6,6,4의 순서일 경우, 6점을 받은 두 사람은 공동 3등이 되고, 그 다음 순서인 4점을 받은 사람은 5등이 된다. 이 규칙을 다르게 표현하면 다음과 같다: 각 사람마다 “나보다 점수가 큰 사람”의 수를 세어 1을 더한 것이 자신의 등수가 된다. 대회별 등수는 각 대회에서 얻은 점수를 기준으로 하며 최종 등수는 세 대회의 점수의 합을 기준으로 한다.

각 참가자의 대회별 등수 및 최종 등수를 출력하는 프로그램을 작성하시오.

 

2. 제약조건

3 ≤ N ≤ 100,000

 

3. 입력

첫째 줄에 참가자의 수를 나타내는 정수 N이 주어진다.
이어 세 개의 줄에 각 대회의 결과를 나타내는 N개의 정수가 주어진다. 이중 i번째 정수는 그 대회에서 i번째 사람이 얻은 점수를 의미한다.

4. 출력

첫 세 개의 줄에는 각 참가자의 대회별 등수를 출력한다. 즉 이중 c번째 줄의 i번째 정수는 c번째 대회에서의 i번째 사람의 등수를 의미한다.
이어 새로운 줄에 같은 형식으로 각 참가자의 최종 등수를 출력한다.

 

---

 

5. 풀이

for문으로 하나씩 풀어갈까도 생각했지만 제약조건을 보면 N이 10만회인 걸 보면 시간복잡도에서 이미 통과하지 못할 것이다. (10만 x 2(대회 1회당) x 4(4번 등수 출력) = max 60만회)

그래서 나는 우선순위 큐로 가장 점수가 높은 순서로 하나씩 뽑을 수 있도록 했다.

from queue import PriorityQueue
rank = [1] * 100001 # rank[i] : 점수 i에 대한 현재 등수

N = int(input())

que = PriorityQueue(maxsize=N)
final = [0] * 100001

def que_check(que):
    before = 0
    count = 0

    while not que.empty():
        num = que.get()[1]
        count += 1  # count번째 사람 확인
        # print(num, count)

        if num < before: # 이번에 꺼낸 수가 전에 꺼낸 수보다 작으면
            rank[num] = count
        before = num
# 총 3회 대회
for i in range(3):
    data = list(map(int,input().split()))

    for i in range(len(data)):
        que.put((-data[i], data[i])) # 점수 내림차순 정렬
        final[i] += data[i] # 성적 입력을 받을 때마다 각 사람들의 점수를 별도로 저장

    que_check(que)

    for i in range(N):
        if i == N - 1:
            print(rank[data[i]], end='')
        else:
            print(rank[data[i]], end=' ')
    print()
    # 등수 출력 후 등수는 처음부터 다시 초기화
    rank = [1] * 100001

for i in range(N):
    que.put((-final[i], final[i]))  # 점수 내림차순 정렬

que_check(que)

for i in range(N):
    if i == N-1:
        print(rank[final[i]], end='')
    else:
        print(rank[final[i]], end=' ')

• rank[i] : 점수 i에 대한 현재 등수를 저장

코드 구조상 우선순위 큐에서 꺼낸 순서에 따라서 등수가 정해질 수 밖에 없어서 점수를 꺼낼 때마다 현재 등수를 한번씩 올리게 했고 이번에 꺼낸 수가 바로 이전에 꺼낸 수보다 적은 점수면 현재 순위를 rank 변수에 저장하도록 했다. 이렇게 하면 이전에 꺼낸 점수보다 크거나 같다면 앞에서 꺼냈을 때의 등수와 같은 등수를 현재 점수에 지정해줄 수 있다.

 

최종 점수도 위와 같은 방식으로 지정 해주도록 하면 끝