[정렬 알고리즘] 성적이 낮은 순서로 학생 출력하기 - 파이썬(python)

성적이 낮은 순서로 학생 출력하기

난이도 : 下 풀이 시간 : 20분

시간 제한 : 1초 메모리 제한 : 128 MB

 

---

 

해답

 

n = int(input())
array = []

for i in range(n):
    input_data = input().split()

    array.append((input_data[0], int(input_data[1])))

array = sorted(array, key = lambda x:x[1])

for x in array:
    print(x[0], end = ' ')

---

예시

 

# N 입력 받기
n = int(input())

# N명의 학생 정보를 입력 받아 리스트에 저장
array = []
for i in range(n):
    input_data = input().split()
    # 이름은 문자열 그대로, 점수는 정수형으로 변환하여 저장
    array.append((input_data[0], int(input_data[1])))

# 키(Key)를 이용하여, 점수를 기준으로 정렬
array = sorted(array, key=lambda student: student[1])

# 정렬이 수행된 결과를 출력
for student in array:
    print(student[0], end=' ')

 

---

해설

 

학생의 정보가 최대 100,000개까지 입력될 수 있으므로 최악의 경우 O(NlogN)을 보장하는 알고리즘을 이용하거나 O(N)을 보장하는 계수 정렬을 이용하면 됩니다.
입력되는 데이터는 이름과 점수지만 출력할 때는 이름만 출력하면 되므로 학생 정보를 (점수, 이름)으로 묶은 뒤에 점수를 기준으로 정렬을 수행해야 합니다.
따라서 튜플 자료형과 더불어 파이썬의 기본 정렬 라이브러리를 사용하는게 효과적입니다.