[백준 알고리즘] 10814 - 나이순 정렬

N=int(input())

person=[]

for i in range(N):
    age,name=list(map(str, input().split()))

    person.append([int(age),i, name])

person.sort()

for i in range(N):
    print(str(person[i][0])+" "+person[i][2])

예제 입력

3
21 Junkyu
21 Dohyun
20 Sunyoung

예제 출력

20 Sunyoung
21 Junkyu
21 Dohyun

떠올린 접근 방식, 과정

age랑 name을 일단 str로 따로 입력받은 후 person에다가 age는 int, name은 str그대로 넣어주어 배열을 순서대로 정렬한 후 출력해준다.

해당 접근 방식에 쓰이는 알고리즘과 판단 사유

정렬을 위해 sort를 사용했다. sort는 시간복잡도가 NlogN으로 가장 빠르다고 생각했다.

접근법의 총 시간복잡도

sort의 시간복잡도인 O(NlogN)이라고 생각한다.

(에러 오류가 발생했다면) 해결 과정

오류 코드

N=int(input())

person=[]

for i in range(N):
    age,name=list(map(str, input().split()))

    person.append([int(age), name])
    person.sort()

for i in range(N):
    print(person[i])

먼저 시간 초과를 해결하려했다. sort를 for문 내부에 넣어놔서 sort가 N번이나 돌아갔었다. 그래서 sort를 밖으로 빼내주고 제출했더니 틀렸다고 나왔다.

input 순서대로 정렬을 안해줬기 때문인데 어떻게 해결해야할 지 막막할 때 근성이가 도와줬다.

person에 넣을 때 age 랑 name 사이에 i를 넣어주면 input 순서가 빠를수록 i는 작고 age가 같을 경우엔 i로 비교하니깐 들어온 순으로 정렬할 수 있게 되었다.

print할때에는 i를 빼고 출력해주면 된다.

개선 방법

배열 내부에 임의의 값을 넣는 것을 두려워하지 말고, 출력할 때만 제대로 출력해주면 된다.