[백준 10814번] 나이순 정렬

📌 문제

👊 백준 10814번 - 나이순 정렬

---

📌 개념

sorted dict

• sorted(iterable, key = ~) : 설정한 key의 속성에 따라 정렬해준다.
• sorted(iterable, key = lambda x : x[0]) : x[0]의 값을 기준으로 iterable을 정렬한다.

---

❎ 첫번째 시도 (시간초과)

❌ 시간초과로 통과되지 못한 코드이다 😥

• 

• 선택 정렬을 사용해 정렬했다.
• arr이라는 dict를 사용했다. dict의 value 값은 나이, 이름, 입력 순서(i)에 대한 정보를 담은 list이다.
• arr[i][0]는 나이, arr[i][1]은 이름, arr[i][2]는 입력 순서에 대한 값이다.
• 기본적으로는 age(arr[0])를 기준으로 선택 정렬하였다. 단, age의 값이 같을 경우, arr[i][2]의 값을 비교하여 더 작은(더 먼저 입력된) 값이 앞에 오도록 해주었다.

Code

test_case = int(input())
arr = {}
for i in range(test_case):
    age, name = input().split(" ")
    arr[i] = [int(age), name, int(i)]

for i in range(test_case):
    min = i
    for j in range(i + 1, test_case):
        if arr[min][0] == arr[j][0]:  # 나이가 같으면
            if arr[min][2] > arr[j][2]:  # 더 앞에 있는(index 값이 작은) 사람이 앞에
                min = j
        if arr[min][0] > arr[j][0]:  # 나이가 더 적은 사람이 min
            min = j
    arr[min], arr[i] = arr[i], arr[min]

for i in arr:
    print("{} {}".format(arr[i][0], arr[i][1]))

+ 시간 초과 이유

• 선택 정렬의 $Big-O$ 시간 복잡도는 $O(n^2)$이다.
• 파이썬 기본 라이브러리의 정렬(sort) 함수의 시간 복잡도는 $O(nlogn)$이다.

  

  • $O(1) < O(log n) < O(n) < O(nlog n) < O(n^2) < O(2^n) < O(n!)$

---

✅ 문제 해결

• [age, name]의 정보를 입력받아 2차원 list로 저장한다.
  [[20, 'Sunyoung'], [21, 'Junkyu'], [21, 'Dohyun']]
• 파이썬의 기본 정렬 라이브러리를 이용하여 나이를 기준으로 정렬한다.
• 나이를 기준으로 정렬하는 방법은 sorted의 key의 속성을 나이로 설정하면 된다.
• 나이가 같은 경우, 파이썬 기본 정렬 라이브러리 자체적으로 먼저 입력받은 값이 먼저 정렬되도록 설정한다.

Code

n = int(input())
arr = []
for _ in range(n):
    input_data = input().split(" ")
    arr.append([int(input_data[0]), input_data[1]])

arr = sorted(arr, key=lambda x: x[0])

for num in arr:
    print("{} {}".format(num[0], num[1]))