[파이썬/Python] 백준 10814번: 나이순 정렬

숨·2024년 6월 26일

알고리즘 문제 풀이

목록 보기

2/105

📌 문제 : 백준 10814번

📌 문제 탐색하기

N : 온라인 저지 회원의 수 (1 ≤ N ≤ 100,000)
age : 회원의 나이 (1 ≤ age ≤ 200)
name : 이름 (알파벳 대소문자, len(name) ≤ 100)
+ age, name 입력 순서 = 가입한 순서를 의미한다.

원하는 출력 조건

회원들을 나이 증가하는 순(=오름차순)으로 출력
나이가 같다면 먼저 가입한 사람이 앞에 오도록 출력

입력이 age, name 2가지이므로 [age, name] 형식의 2차원 배열로 저장한다.

2가지 조건으로 정렬해야 하므로

입력이 age, name 2가지이고 입력된 순서도 고려해야 한다.

순서를 의미하는 idx를 정의하여 입력마다 1씩 증가시켜서 {idx : [age, name]} 형식의 딕셔너리로 저장한다.

sort() 함수를 통해 2가지 조건으로 정렬한다.
→ 1순위 : age, 2순위 : idx

딕셔너리의 Key, Value 쌍을 얻기 위해 items() 함수를 활용한다.

[(idx, [age, name]), … ]의 튜플로 묶은 값을 얻은 후, lambda 식을 통해 정렬 기준을 작성하여 sorted() 함수로 정렬한다.

정렬 후의 딕셔너리를 원하는 형식으로 출력하기 위해 for문으로 출력한다.

가능한 시간복잡도

for문을 돌면서 N만큼 입력받기 → $O(N * len(입력))$
sorted()로 정렬 → $O(NlogN)$
for문을 돌면서 N만큼 출력하기 → $O(N)$

최종 시간복잡도
$O(N * len(입력) + NlogN) = O(N * len(입력))$ 이다.
주어진 조건에 따라 입력의 길이는 최대 3(age가 세자리수) + 1(공백) + 100(name 길이)= 104가 된다.
최악의 경우 10,400,000번의 연산을 하게 되는데 시간 제한 안에 연산이 가능하다.

알고리즘 선택

딕셔너리를 sorted()로 2가지 기준을 가지고 정렬하는 방식 선택.

📌 코드 설계하기

정수 N 입력받기
N만큼 반복하여 회원 이름, 나이를 인덱스와 함께 딕셔너리로 입력받기
2가지 기준으로 sorted()로 정렬
원하는 형식으로 출력

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

1회차

입력받은 age의 자료형을 지정하지 않아서 문자열 상태로 정렬하다보니 두자리 수 이상의 age를 입력받았을 때 정렬이 제대로 되지 않는 문제가 발생했다. 자료형을 int로 해주었더니 에러가 해결되었다.

📌 정답 코드

import sys

input = sys.stdin.readline

# 1. 정수 N 입력받기
N = int(input())

# 2. N만큼 반복하여 회원 이름, 나이를 인덱스와 함께 딕셔너리로 입력받기
member_dict = {}

for idx in range(N):
    member_dict[idx] = list(input().split())

# 3. 2가지 기준으로 sort()로 정렬
sorted_member_dict = dict(sorted(member_dict.items(), key=lambda x: (int(x[1][0]), x[0])))

# 4. 원하는 형식으로 출력
for value in sorted_member_dict.values():
    print(f'{value[0]} {value[1]}')

결과

추가 풀이

딕셔너리로 푸는 것이 복잡해서 다른 방법을 찾아보니 굳이 입력 순서를 위해 idx를 따로 저장하지 않아도 해결할 수 있다는 것을 알았다.
- 파이썬의 sorted(), sort()함수가 안정적인 정렬을 한다는 것을 배웠다.
  - 안정 정렬(Stable Sort) : 중복된 값은 입력 순서와 동일하게 유지해 정렬
  - 불안정 정렬(Unstable Sort) : 중복된 값은 입력 순서와 상관없이 무작위로 뒤섞인 상태에서 정렬

코드

import sys

input = sys.stdin.readline

# 1. 정수 N 입력받기
N = int(input())

# 2. member를 리스트로 입력받기
members = [list(map(str, input().split())) for _ in range(N)]

# 3. 정렬하기
members.sort(key=lambda x: int(x[0]))

# 4. 원하는 형식으로 출력하기
for member in members:
    print(*member)