[python/백준] 5635. 생일(S5)

📌 문제 탐색하기

👉 문제바로가기

n: 반에 있는 학생의 수(1<=n<=100)

나이순으로 정렬해야 원하는 이름을 출력할 수 있으므로 다음과 같이 값을 비교해야겠네요.

1. 연도 비교
2. (연도가 같을 경우)월 비교
3. (연도와 월도 같은 경우)일 비교
   👉 여기서 연도, 월, 일 모두 클수록 나이가 적으니까 내림차순 정렬을 사용하면 됩니다.

학생이 여러명이고, 한 학생당 저장할 값이 여러개(이름, 일, 월, 연도)이므로 이중리스트로 구현하는것이 적합할 것 같네요.

정렬의 경우 우선순위를 고려하여 연도->월->일 순으로 정렬을 하면 됩니다.

* 파이썬 다중리스트는 정렬에서 우선순위를 정하는 것이 가능합니다.

가능한 시간복잡도

처음 정렬 시, 즉 연도로 비교하여 정렬 시 sort()를 사용할 경우 시간복잡도는 O(nlogn)입니다. 이후 정렬 시에는 요소 수가 감소할 것이기 때문에 처음 정렬할 때 보다는 시간복잡도가 감소하겠네요. 결론적으로 전체 시간복잡도는 O(nlongn)이 됩니다.

알고리즘 선택

파이썬에서 정렬할 때 쓰는 알고리즘은 크게 두 가지 입니다.
1. sort()
2. sorted()

기존 리스트가 변경되지 않아야 하는 경우를 제외하고는 sort를 사용하는게 더 속도가 빠르기 때문에.. sort()를 사용하는 것으로 선택했습니다.

📌 코드 설계하기

1. 학생의 수 n을 사용자로부터 입력받습니다.
2. n명의 각 학생에 대한 정보(이름, 일, 월, 연도) 쌍을 한 줄에 하나씩 입력받아 리스트에 저장합니다.
3. 다중리스트 우선순위 정렬을 활용하여 연도->월->일의 우선순위로 내림차순 정렬합니다.
4. 정렬된 리스트의 가장 앞에있는 요소에 해당되는 학생의 이름과 가장 마지막에 있는 요소에 해당되는 학생의 이름을 출력합니다.

📌 정답 코드

n = int(input())  # 학생의 수

birth = [list(map(str, input().split())) for i in range(n)]

# 우선순위 정렬(x[3]:연도, x[2]:월, x[1]:일)
birth.sort(key=lambda x: (-int(x[3]), -int(x[2]), -int(x[1])))

print(birth[0][0])
print(birth[n - 1][0])

📌 다른 풀이

아래는 코딩테스트 챌린지 3기 입문반에 참여하여 알게된 다른 풀이 방법입니다.

import sys

# 1. 문제의 입력을 받습니다.
N = int(sys.stdin.readline())
arr = []

def changeToDate(year, month, day):
    if len(month) == 1:
        month = '0' + month
    if len(day) == 1:
        day = '0' + day
    return year + month+day


for _ in range(N):
    name, day, month, year = sys.stdin.readline().split()
    arr.append([changeToDate(year,month,day), name])

# 3. arr를 정렬합니다.
arr.sort()

# 4. 정답을 출력합니다.
print(arr[len(arr)-1][1]) # 나이가 가장 적은 사람
print(arr[0][1]) # 나이가 가장 많은 사람

👉 1차원 배열 정렬 활용

참고

• 파이썬 input과 sys.stdin.readline()
• 입력속도비교_백준

📌 내용 정리

1. input()과 sys.stdin.readline()

• 한 줄을 입력받을 경우 input()을 사용해도 괜찮지만, 반복문으로 여러줄을 입력받는 상황에서는 시간 초과를 방지하기 위해 속도가 더 빠른 sys.stdin.readline()를 사용하는 것이 좋습니다.

2. 다차원 배열을 정렬하면 앞의 열부터 우선 순위를 가지고 정렬됩니다.

3. 다차원 배열보다는 1차원 배열의 정렬을 수행할 때 시간이 훨씬 절약됩니다. 다차원 배열로 풀 수 있는 문제인 경우 1차원 배열로 바꿀 수 있는지 생각해보면 좋을 것 같습니다.