[python/백준] 10814. 나이순 정렬(S5)

Rose·2024년 8월 6일

백준 코테

백준

목록 보기

2/27

📌 문제 탐색하기

👉 문제바로가기

N: 온라인 저지 회원의 수 (1 ≤ N ≤ 100,000)

age(정수), name(문자열): 각 회원의 나이와 이름이 N개의 줄에 입력되므로 반복문을 사용하여 입력받아 저장합니다.

나이와 이름 쌍을 저장해야 하기 때문에 자료형은 딕셔너리나 리스트가 적합해보입니다.

그러나 나이와 이름이 중복될 경우를 생각하면 딕셔너리의 경우 key 중복 시 중복되는 요소가 출력되지 않을 것이므로 리스트가 적합하다는 결론을 내렸습니다.

가능한 시간복잡도

파이썬에 내장되어있는 sort()는 TimSort알고리즘을 사용합니다.
Timsort는 병합 정렬과 삽입 정렬을 결합한 정렬 알고리즘이며, 평균 및 최악의 경우 시간복잡도 O(NlogN)을 보장합니다.
- Timsort는 작은 데이터 세트에 대해 매우 효율적이며, 삽입 정렬을 같이 사용해 병합 정렬의 시간복잡도를 줄인 알고리즘입니다.

알고리즘 선택

리스트 쌍 중 한가지 요소(age)로만 정렬하면 됩니다.
리스트를 정렬하는 방법 중 sort(), sorted()
- sort함수는 리스트명.sort()형식으로 “리스트형의 메소드”이며 리스트 원본값을 직접 수정합니다.
- sorted함수는 sorted(리스트명) 형식으로 “내장 함수”이며 리스트 원본 값은 그대로이고 정렬 값을 반환합니다.
- 리스트의 원본 값을 유지할 필요가 없기 때문에 sort()를 사용해도 됩니다.

📌 코드 설계하기

온라인 저지 회원의 수 N을 입력받습니다.
회원의 수 N만큼 반복하여 회원 나이와 이름을 받아 2차원 리스트의 요소로 추가합니다.
- 이 때 나이는 정수로 입력받는다는 것을 설계 단계에 적지 않아 문자열로 출력하게 되는 문제가 발생
2차원 리스트에서 각각의 첫번째 요소를 key로 지정(key=lambda x: x[0])하여 정렬합니다.
출력 형식에 맞게 요소를 출력합니다.

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

1회차: 런타임 에러 발생

N = int(input())  # 회원의 수
member = {}  #key: name, age:value
for _ in range(N):
	age, name = map(str, input().split())
	age = int(age)
	member[name] = age

#age(value)를 기준으로 정렬
sorted_member = sorted(member.items(), key=lambda x: x[1])

for i in range(N):
	for j in range(1, -1, -1):
		print(sorted_member[i][j], end=' ')
	print()

2회차: 반례

N = int(input())  # 회원의 수
member = {}  #key:name, age:value

for _ in range(N):
  age, name = map(str, input().split())
  age = int(age)
  member[name] = age

#age(value)를 기준으로 정렬
sorted_member = dict(sorted(member.items(), key=lambda x: x[1]))

for name, age in sorted_member.items():
  print(age, name)

반례 발생 원인

해당 코드에서는 name을 key로 설정하였기 때문에 name이 같은 경우 자동으로 중복이 제거됩니다.

3회차: 자료형 문제

N = int(input())  # 회원의 수
member = [list(map(str, input().split())) for _ in range(N)]  # 2차원 리스트 생성

member.sort(key=lambda x: x[0])

for i in range(N):
  for j in range(2):
    print(member[i][j], end=' ')
  print()

나이와 이름을 위와 같이 함께 입력받는 경우 모두 문자열이 됩니다. 나이는 정수형이어야 하므로 입력받은 후 int함수를 활용하여 정수로 변경하였습니다.

📌 정답 코드

N = int(input())  # 회원의 수
member = []  # 회원리스트

for _ in range(N):
  age, name = map(str, input().split())  # 2차원 리스트 생성
  member.append([int(age), name])

member.sort(key=lambda x: x[0])

for i in range(N):
  for j in range(2):
    print(member[i][j], end=' ')
  print()