파이썬 Python | 알고리즘 | 백준 생일

⭕ 파이썬 Python | 알고리즘 | 백준 생일

➡️ 문제링크

• https://www.acmicpc.net/problem/5635

 

➡️ 문제 탐색하기

• 모든 학생을 서로 비교하며 가장 나이가 많은 학생과 가장 어린 학생을 찾는 방식은  O(N^2) 시간 복잡도를 가지므로, N이 작을 때는 효율적이지만 N이 커질수록 비효율적인 방식이 된다. 따라서 학생 리스트를 정렬한 후, 첫 번째와 마지막 학생을 출력하는 방식으로 O(N log N) 시간 복잡도를 가지는 정렬 알고리즘을 선택했다.
• 생일 정보는 '이름, 일, 월, 연도' 형태로 주어지며, 이를 2차원 배열로 저장하여 정렬한다. 정렬 기준은 연도 -> 월 -> 일 순으로 오름차순 정렬하여 생일이 빠를수록 배열의 앞쪽에 오게 한다.
  • 입력 데이터는 행 * 4열의 2차원 배열로 저장한다.
  • 람다식을 사용하여 2열(일)을 기준으로 오름차순 정렬한다.
  • 람다식을 사용하여 3열(월)을 기준으로 오름차순 정렬한다.
  • 람다식을 사용하여 4열(연도)을 기준으로 오름차순 정렬한다.
• 정렬이 완료된 배열에서 가장 나이가 많은 사람은 배열의 첫 번째 행에, 가장 어린 사람은 마지막 행에 위치하게 된다.

 

➡️ 코드 설계하기

• 파이썬의 sort 함수는 Timsort 알고리즘을 사용하며, 시간 복잡도는 O(N log N)이다. 학생의 수가 최대 100명이므로, 최악의 경우 3번의 정렬을 수행하더라도 연산량은 최대 300 * log 100 수준으로 매우 작다. 따라서 성능상 문제는 없다고 판단된다.

 

 

➡️ 시도 회차 수정 사항 (Optional)

1회차

• 시간 100ms
• 입력을 받아 3번의 정렬을 수행했다. O(n log n) 정렬을 3번 수행하여 상수 시간이 3배로 늘어 실제 실행 시간이 길어질 수 있다고 생각한다.

import sys

number = int(sys.stdin.readline())

members = []

for i in range(number):
    name, dd, mm, yyyy = sys.stdin.readline().split()
    members.append([name, int(dd), int(mm), int(yyyy)])

members.sort(key=lambda x: x[1])
members.sort(key=lambda x: x[2])
members.sort(key=lambda x: x[3])


print(members[number-1][0])
print(members[0][0])

---

2회차

• 시간 88ms
• 한 번의 정렬로 해결하도록 변경하여 실행 시간을 개선했다. 정렬을 한 번만 수행하도록 수정하여 상수 시간을 줄였다.

import sys

number = int(sys.stdin.readline())

members = []

for _ in range(number):
    name, dd, mm, yyyy = sys.stdin.readline().split()
    members.append([name, int(dd), int(mm), int(yyyy)])

members.sort(key=lambda x: (x[3], x[2], x[1]))

print(members[-1][0])
print(members[0][0])

---

3회차

• 시간 84ms
• 다차원 배열보다는 1차원 배열의 정렬을 수행할 때 시간이 훨씬 절약된다. 다차원 배열로 풀 수 있는 문제인 경우 1차원 배열로 바꿀 수 있는지 생각해보면 좋을 것같다.
• year, month, day 정보를 yyyymmdd 형태로 변경하여 1차원 배열을 정렬하는 방법도 있다. month가 1자리, day가 1자리 일 경우 들에 대해 처리하여 정확한 `yyyymmdd`를 만들고, 이 값을 배열에 넣어 정렬하면 된다.

import sys

number = int(sys.stdin.readline())

members = []

for _ in range(number):
    name, dd, mm, yyyy = sys.stdin.readline().split()
    if (len(dd) == 1):
        dd = "0" + dd
    if (len(mm) == 1):
        mm = "0" + mm
    yyyymmdd = yyyy + mm + dd
    
    members.append([name, int(yyyymmdd)])

members.sort(key=lambda x: x[1])

print(members[-1][0])
print(members[0][0])

 

 

➡️ 정답 코드

import sys

number = int(sys.stdin.readline())

members = []

for _ in range(number):
    name, dd, mm, yyyy = sys.stdin.readline().split()
    if (len(dd) == 1):
        dd = "0" + dd
    if (len(mm) == 1):
        mm = "0" + mm
    yyyymmdd = yyyy + mm + dd
    
    members.append([name, int(yyyymmdd)])

members.sort(key=lambda x: x[1])

print(members[-1][0])
print(members[0][0])