백준 24509 - 상품의 주인은? (Python)

24509 상품의 주인은?

 

문제

혜민이네 반은 총 N$N$명의 학생으로 이루어져 있으며 학생마다 번호가 다르게 배정되어 있다.

이번 시험은 국어, 영어, 수학, 과학 총 4과목으로 진행되며,

학생들이 공부를 열심히 할 수 있게 과목별 1등에게 상품을 주기로 했다.

 

수상은 국어, 영어, 수학, 과학 순서로 하며 최대한 많은 학생에게 상품을 주고 싶기 때문에 학생마다 상품은 한 번만 받을 수 있다.

 

예를 들어 국어 과목에서 1등 한 사람이 수학 과목에서 또 1등을 한다면

국어 과목에서 상품을 받았기 때문에 이 학생은 다른 과목에서 상품을 더 받을 수 없다.

 

따라서 수학 과목은 상품을 받지 않은 학생 중에 점수가 가장 높은 학생이 상품을 받는다.

단, 동점이 있으면 번호가 빠른 사람이 상품을 받는다. 과목별 상 받을 사람의 번호를 출력하시오.

입력

첫 번째 줄에 학생의 수 N(4≤N≤200,000)이 주어진다.

두 번째 줄부터 N+1번째 줄까지 N개의 줄에 걸쳐서 학생의 번호 X(1≤X≤N)와

학생의 국어 점수 A, 영어 점수 B, 수학 점수 C, 과학 점수 D가

순서대로 공백을 기준으로 정수로 주어진다.

학생의 번호는 중복될 수 없다. (0≤A,B,C,D≤100)

출력

국어, 영어, 수학, 과학 순서대로 상품을 받는 학생의 번호를 공백으로 구분하여 출력한다.

 

문제풀이

이번 문제는 전형적인 정렬 문제였다.

 

학생은 한 개의 과목에 대해서만 상을 수상할 수 있으며,

동점자는 번호가 빠른 순으로 받게 된다.

 

과목은 총 4개이며, 국어부터 차례로 수상한다.

 

그렇다면 우리는, 각 과목별로 점수가 높은 순서를 알아내고,

그 때의 학생의 번호를 기준으로 한 번 더 정렬해주면 된다.

 

두 개의 키 값을 기준으로 배열을 정렬해주고,

중복되지 않도록 학생의 번호를 하나씩 쌓아주면 된다.

 

매 과목에서 정렬을 수행해주면서 점수가 높은 사람을 찾아내주면 된다.

배열에 이미 들어가 있는 사람이면 넘어가고, 그렇지 않으면 넣어주면서 수상자를 정리해주면 된다.

정답코드

### 24509

n = int(input())

total = []
answer = []

for i in range(1, n+1):
    scores = list(map(int, input().split()))
    total.append(scores)

for sub in range(1, 5):
    sorted_total = sorted(total, key=lambda x: (-x[sub], x[0]))
    
    for one in sorted_total:
        if str(one[0]) in answer:
            continue
        else:
            answer.append(str(one[0]))
            break

print(' '.join(answer))