[백준 / python] 10814번 나이순 정렬

오늘은 정렬 알고리즘이 필요한 백준 10814번 문제, 나이순 정렬을 풀어보겠습니다!

 

< 문제 확인 >

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

---

📌 문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

 

회원들을 나이 기준으로 오름차순 정렬하고, 나이가 같은 경우에는 가입한 순서대로 정렬하여 출력한다.

 

최종적으로 구해야하는 정답은 위의 내용처럼 기준에 맞게 출력하는 것이다.

 

이 문제를 해결하기 위해서는 입력받은 회원들의 정보를 리스트에 저장하고,

나이 기준으로 정렬한 후 나이가 같은 경우에는 가입 순서대로 출력해야 한다.

 

정렬과 관련된 여러 아이디어 중에서 파이썬 내장 정렬 함수인 Timsort를 사용할 수 있을 것이다.

 

가장 중요한 부분은 나이가 같을 경우를 대비하여

인덱스 번호를 추가하여 가입한 순서를 알 수 있어야한다!!

 

⭐️ (나이, 이름, 인덱스 번호) ⭐️

 

✔️ 가능한 시간복잡도

N이 최대 100,000이므로, O(Nlog⁡N) 시간 복잡도를 가지는 정렬 알고리즘을 사용해야 한다.

 

✔️ 알고리즘

 

리스트에 (나이, 이름, 원래 인덱스) 튜플을 저장하여 나이와 원래 인덱스를 기준으로 정렬한다.

그리고 Python의 내장 정렬 기능인 sort()를 이용해 튜플을 정렬한다.

이 때, key 파라미터를 이용해 나이와 원래 인덱스 기준으로 정렬할 수 있다.

 

 

---

📌 코드 설계하기

- 문제 탐색하기 과정을 기반으로 이 문제를 해결하기 위한 로드맵을 그리는 과정
- 어떤 순서로 코드를 작성해야 할지, 어떤 함수들을 작성해야 할지 등을 작성

 

1. 사용자가 회원수를 먼저 입력하고, 이어서 나이와 이름을 입력한다.

2. 회원 정보를 리스트에 저장하고, 가입 순서를 확인할 수 있는 인덱스 번호도 함께 저장한다.

3. 리스트를 나이 기준으로 정렬하고, 나이가 같을 경우 인덱스 번호 순서대로 정렬되도록 한다.

4. 최종적으로 회원들의 나이순 정렬 결과를 출력한다.

 

---

📌 시도 회차 수정 사항 (Optional)

무문별하게 “맞았습니다”가 나올때 까지 수정하는 형태의 문제 풀이를 반복하면,

내가 어떤 실수를 해서 해당 문제를 틀렸는지 모른다.

- 틀렸습니다를 받았다면 왜 틀렸는지, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검

 

---

📌 정답 코드

import sys

input = sys.stdin.read
data = input().splitlines()

# 회원 수 입력
N = int(data[0])

# 회원 정보를 저장할 리스트
members = []

for i in range(1, N + 1):
    age, name = data[i].split()
    age = int(age)
    members.append((age, name, i - 1))  # (나이, 이름, 인덱스 번호)

# 나이 기준으로 정렬하고 나이가 같으면 인덱스 번호를 기준으로 정렬
members.sort(key=lambda x: (x[0], x[2]))

# 정렬된 최종 결과 출력
for member in members:
    print(member[0], member[1])

 

기초적인 정렬 알고리즘 문제를 더 풀어보면서 보완해야할 것 같다 ㅠㅠ

 

 

코테 챌린지 3기 파이팅 :)

@why_dev_says_no