국영수(p.359) - 정렬 문제(이코테)

---

해설 부분은 책의 내용을 포함하고, 더 추가하여 최대한 자세하게 설명하려고 노력했습니다.

---

 

문제 설명 

 

도현이네 반 학생 N명의 이름과 국어, 영어, 수학 점수가 주어집니다. 이때, 다음과 같은 조건으로 학생의 성적을 정렬하는 프로그램을 작성하세요. 

 

1. 국어 점수가 감소하는 순서로
2. 국어 점수가 같으면 영어 점수가 증가하는 순서로
3. 국어 점수와 영어 점수가 같으면 수학 점수가 감소하는 순서로
4. 모든 점수가 같으면 이름이 사전 순으로 증가하는 순서로 (단, 아스키코드에서 대문자는 소문자보다 작으므로 사전 순으로 앞에 옵니다.) 

 

입력 조건

 

• 첫째 줄에 도현이네 반의 학생 수 N(1 <= N <= 100,000)이 주어집니다. 
• 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어집니다.
• 점수는 1보다 크거나 같고, 100보다 작거나 같은 자연수입니다. 
• 이름은 알파벳 대소문자로 이루어진 문자열이고, 길이는 10자리를 넘지 않습니다. 

 

출력 조건

 

• 문제에 나와 있는 정렬 기준으로 정렬한 후 첫째 줄부터 N개의 줄에 걸쳐 각 학생의 이름을 출력합니다. 

 

입력 예시 

 

12
Junkyu 50 60 100
Sangkeun 80 60 50
Sunyoung 80 70 100
Soong 50 60 90
Heabin 50 60 100
Kangsoo 60 80 100
Donghyuk 80 60 100
Sei 70 70 70
Wonseob 70 70 90 
Sanghyun 70 70 80 
nsj 80 80 80
Taewhan 50 60 90

 

 

출력 예시 

 

Donghyuk
Sangkeun
Sunyoung
nsj
Wonseob
Sanghyun
Sei
Kangsoo
Heabin
Junkyu
Soong
Taewhan

 

 

---

 

 

문제 해설

 

문제 설명에 나온 4가지 기준으로 입력값을 정렬해서 출력하는 정렬 문제다. 문자열과 숫자가 함께 입력이 되는데 파이썬에선 기본 입력값을 문자열로 인식하니까 숫자 부분 정렬할 때는 int() 함수를 사용해서 순서를 구분한다. 파이썬의 정렬 기능인 sort() 함수와 lambda 함수를 이용하면 깔끔하게 한 줄로 구현할 수 있지만, 이런 기능을 지원하지 않는 다른 언어라면 조금 더 어렵지 않을까 하는 생각이 들었다. 

 

책에서 제시하는 해설 코드는 다음과 같다. 

 

import sys 
n = int(input()) 
students = []
for i in range(n):
    students.append(sys.stdin.readline().split()) 

""" [정렬 기준] 
1) 두 번째 원소를 기준으로 내림차순 정렬
2) 두 번째 원소가 같은 경우, 세 번째 원소를 기준으로 오름차순 정렬
3) 세 번째 원소가 같은 경우, 네 번째 원소를 기준으로 내림차순 정렬 
4) 네 번째 원소가 같은 경우, 첫 번쨰 원소를 기준으로 오름차순 정렬
 """

# 튜플로 정렬
students.sort(key = lambda x : ( -int(x[1]), int(x[2]), -int(x[3]), x[0] ) ) # 그래야지 여러 조건 가능

# 정렬된 학생 정보에서 이름만 출력
for student in students:
    print(student[0])

 

여러 줄을 연속적으로 입력받아서 input()을 sys.stdin.readline() 으로 바꿔봤다. 입력받는 줄이 길지 않아서 input()으로 했어도 문제없을 듯싶다. 학생들의 정보를 입력받기 위해 students라는 빈 리스트를 생성했다. 그리고 for문으로 입력값을 받은 후 문제 설명에서 주어진 방식대로 정렬을 한다. 앞에서 말했지만 파이썬에서 지원하는 sort() 함수와 lambda 함수를 이용한다. sort() 함수는 O(NlogN) 복잡도를 보장하니 대부분의 경우에서 사용이 가능하다. lambda 함수는 key= 키워드와 함께 사용한다. 순서는 이름, 국어 점수, 영어점수, 수학 점수 순으로 입력이 되니, 그대로 정렬을 해주면 된다. 

 

첫째로 국어 점수가 감소하는 순서니까 x[1]을 int() 함수 사용해 숫자로 바꾸고 내림차순이니 앞에 '-'를 붙인다. 

 

두 번째 국어 점수가 같으면 영어 점수가 증가하는 순서니까 x[2]에서 int()로 묶으면 된다.(sort() 함수는 기본으로 오름차순 정렬) 

 

세 번째는 국어, 영어 점수가 같으면 수학 점수가 감소하는 순서니까 x[3]에서 int() 함수로 묶고 내림차순이니까 '-'를 붙여준다. 

 

마지막으로 이름이 사전 순으로 증가하는 순서니까 x[0]을 넣어주면 알아서 소문자, 대문자 순서대로 정렬해준다. 

 

그것을 한줄로 적으면 

 

students.sort(key = lambda x : ( -int(x[1]), int(x[2]), -int(x[3]), x[0] ) )

 

이렇게 된다. 깔끔하게 여러 줄의 조건을 만족시킬 수 있다. 아마 c++이나 Java였으면 좀 더 긴 코드가 되지 않았을까 라는 생각이 든다. 

 

이렇게 정렬을 하고 마지막은 for문을 이용해 튜플[0]의 원소인 학생 이름만 줄 바꿈으로 출력해주면 된다. 

 

 

하지만, 더 이해하기 쉽게 코드를 바꾸어보자.

 

import sys 
n = int(input()) 
students = []
for i in range(n):
    a, b, c, d = list(sys.stdin.readline().split())
    students.append([a, b, c, d])

students.sort(key = lambda x : ( -int(x[1]), int(x[2]), -int(x[3]), x[0] )) 

for student in students:
    print(student[0])

 

처음 이름, 국어, 영어, 수학 점수를 입력받을 때 a, b, c, d 변수로 입력 받고, 변수를 모은 리스트를 students 리스트에 하나씩 넣는 방법을 사용했다.

 

* 파이썬은 튜플로 이루어진 리스트가 있을때 튜플의 원소에 맞게 정렬하면, 리스트 전체가 같이 정렬이 되는 특징이 있어서 다음과 같은 풀이가 가능합니다.

 

한가지 예시를 더 들어봅시다.

 

a = [ [5, 1, 5], [3, 5, 5], [3, 1, 9], [3, 1, 1] ]

a.sort(key= lambda x : ( x[1], x[0], x[2]) )
print(a, end=" ")

 

리스트 a는 리스트 안의 원소로 리스트 들을 가지고 있습니다. 리스트 a를 정렬하는 방법에서도 key= lambda 함수를 이용하려면 리스트 내부의 내부 원소를 정렬하는 것이니 튜플로 묶어서 정렬이 가능합니다.

 

이 코드의 결과는 이렇게 나오게 됩니다.

 

[[3, 1, 1], [3, 1, 9], [5, 1, 5], [3, 5, 5]]

 

* 이중 리스트 내부의 원소를 튜플로 정렬해야 원하는 값을 얻을 수 있습니다.

 

 

https://www.acmicpc.net/problem/10825 

10825번: 국영수

 

10825번: 국영수