[백준] 10825번 국영수 - Python(1편)

아래는 백준 10825번 문제입니다. 클릭하면 문제풀이 링크로 넘어갑니다.

백준 10825번 국영수 문제입니다. 클릭하면 문제풀이 링크로 넘어갑니다.

이 문제는 학생들의 이름과 국어, 영어, 수학, 점수를 입력받아 조건에 따라 정렬한 뒤 이름만 출력하는 문제입니다.

1. 국어 점수가 높은 순서로 정렬합니다.
2. 국어 점수가 같다면 영어 점수가 낮은 순서로 정렬합니다.
3. 영어 점수도 같다면 수학 점수가 높은 순서로 정렬합니다.
4. 수학 점수까지 같다면 이름을 사전순으로 정렬합니다.

---

이 문제를 해결하기 위해, Python의 기본 정렬 함수인 sorted()를 사용했습니다. sort()와 sorted()는 Timsort 알고리즘을 기반으로 하여 선형 로그 시간인 O(n log n)의 시간 복잡도를 갖습니다.

파이썬 코딩 테스트를 위한 시간 복잡도 이해하기

 

전체 코드를 먼저 확인하고 자세한 설명으로 들어가겠습니다.

import sys
input = sys.stdin.readline

N = int(input())
data = []

for _ in range(N):
    name, kor, en, math = input().split()
    data.append((name, int(kor), int(en), int(math)))

sorted_data = sorted(data, key=lambda x: (-x[1], x[2], -x[3], x[0]))
result = []
for i in range(N):
    result.append(sorted_data[i][0])

print(*result, sep="\n")

1. 입력 처리

   import sys
   input = sys.stdin.readline
   
   N = int(input())
   data = []

   • 기본 input() 함수 대신 sys.stdin.readline으로 재정의하여 사용했습니다. 아래는 비교값입니다.
     • 기본 input() 사용: 2872ms의 시간이 소요되었습니다.
     • sys.stdin.readline 사용: 324ms의 시간이 소요되었습니다.
     • 입출력 최적화를 통해 실행 시간을 약 9배 정도 단축시킬 수 있었습니다.(실제로 실행해 보면 속도 차이가 어마무시합니다.)
   • 첫 번째 입력값을 정수로 변환하여 변수 N에 저장합니다. 이는 학생 수를 의미합니다.
   • 학생 정보를 저장할 빈 리스트를 생성했습니다.
2. 데이터 입력 및 저장

   for _ in range(N):
       name, kor, en, math = input().split()
       data.append((name, int(kor), int(en), int(math)))

   • 학생 수 만큼 반복하여 데이터를 입력받습니다.
   • 한 줄의 입력값을 공백을 기준으로 나누고 결과를 문자열 리스트로 반환합니다.
     • split()은 문자열 리스트로 반환합니다.
   • 리스트를 각 변수에 언패킹 하여 저장합니다.
   • 이름과 점수들을 튜플 형태로 변환한 뒤 data 리스트에 추가합니다.
     • name을 제외한 나머지 변수들은 문자열을 정수로 변환해 줍니다.
   • 최종적으로 data는 아래와 같은 형태가 됩니다.

     [
         ("Junkyu", 50, 60, 100),
         ("Sangkeun", 80, 60, 50),
         ...
     ]

3. 정렬

   sorted_data = sorted(data, key=lambda x: (-x[1], x[2], -x[3], x[0]))

   • 파이썬의 내장 함수인 sorted()로 리스트를 정렬합니다. 리스트의 메서드인 sort()와 다르게 원본 리스트 data는 변경되지 않습니다.
   • 정렬 기준을 설정합니다. lambda x:는 각 튜플을 인자로 받아 국어(x[1])는 내림차순, 영어 (x[2]) 는 오름차순, 수학 (x[3]) 은 내림차순, 이름 (x[0]) 은 사전순으로 정렬합니다. 누르면 람다 함수에 관한 자세한 설명으로 이동합니다.
4. 결과 추출 및 출력

   result = []
   for i in range(N):
       result.append(sorted_data[i][0])
   
   print(*result, sep="\n")

   1. 빈 리스트를 생성하고 반복문을 돌려 정렬된 리스트의 각 튜플의 첫 번째 요소(이름)를 저장합니다.
   2. 리스트의 모든 요소를 공백 없이 출력하며 각 요소 사이에 줄 바꿈을 삽입합니다.

---

위의 값은 input()을 사용, 아래 값은 sys.stdin.readline을 사용한 결과입니다.

 

결과를 보면 같은 코드지만 입출력 최적화를 통해 시간을 약 9배 정도 단축할 있었습니다.

 

 

# 이 글의 내용 중 일부는 Perplexity AI의 도움을 받아 정보를 수집하고 정리하였으며, 추가적인 연구와 개인적인 견해를 더하였습니다.