[백준 10825번] 국영수 - 파이썬

문제 링크:

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

10825번: 국영수

 

이 문제는 "이것이 코딩 테스트다" 책 유형별 기출문제 23번에 해당한다.

---

풀이 유형:

정렬

 

★문제풀이 Point★

1. 시간 복잡도를 생각한 후 문제 풀기

2. 리스트의 원소들을 정렬할 때는 람다(lambda) 함수 이용

 

풀이 과정:

이 문제는 정렬 문제를 공부하는데 필수로 풀어야 할 문제이다.

문제에서 조건을 살펴보면 N이 최대 100,000이고 시간제한이 1초이다. 이는 O(N^2)으로 풀지 말고 다른 방법으로 풀라는 뜻이다. 파이썬 정렬 라이브러리는 O(NlogN) 시간복잡도를 가지므로 시간 초과가 나지 않고 문제를 풀 수 있다.

따라서 파이썬 정렬 라이브러리인 sort() 함수를 이용하여 lambda 함수로 해결한다.

lambda 함수의 기본 형식은 list. sort(key = lambda x: (정렬 대상)) or sorted(list, key = lambda x: (정렬 대상))이다.

 

답안 예시를 통해 lambda 함수에 대해 이해해보자.

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

리스트의 각 원소(x)가 튜플 형태로 존재할 때 다음과 같은 우선순위에 맞게 원소를 정렬하겠다는 의미이다.

오름차순은 생략, 내림차순은 변수 앞에 -(음수)를 붙여주면 된다.

1. 국어 점수(x[1])가 감소(-)하는 순서로 정렬  =>  -int(x[1])
2. 국어 점수가 같으면 영어 점수가(x[2]) 증가(+)하는 순서로 정렬 => int(x[2])
3. 국어 점수와 영어 점수가 같으면 수학 점수(x[3])가 감소(-)하는 순서로 정렬 => -int(x[3])
4. 모든 점수가 같으면 이름이 사전 순(x[0])으로 증가(+)하는 순서로 정렬 => x[0]

 

★ 이처럼 labmda 함수를 이용하면 특정한 기준으로 정렬하는 대부분의 문제를 해결할 수 있다는 점을 기억하자. ★

 

풀이 코드:

 

# 10825번 국영수
# 4가지 순서대로 정렬
# N이 최대 100000이고 시간 제한 1초이므로, O(N^2)으로 풀면 시간초과 -> O(NlogN)으로 풀어야함.
# 시간복잡도가 O(NlogN)인 파이썬 정렬 라이브러리로 풀기

# 총 학생의 수 입력받기
n = int(input())
students = [] # 학생 정보를 담는 리스트

# 학생과 성적 정보 입력받기
for _ in range(n):
    students.append(input().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])

 

 

10825번 국영수