[백준 10814] 나이 순 정렬

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

10814번: 나이순 정렬

 

이번 문제는 간단한 정렬 관련 문제를 풀어보았다. 먼저 첫 번째 줄에 회원의 수 N을 입력받고 N명의 회원의 나이와 입력을 입력받는다. 다음으로 나이 순으로 출력, 만약 나이가 같다면 먼저 입력된 순으로 출력한다.

 

여기서 만약 나이가 같다면 입력된 순으로 출력하라는 문장을 봤을 때 일단 정렬할 때 key = lambda x: (x [0], x [1])이런 형식으로 lambda를 이용해야 할 것 같다는 생각이 들었다. 위와 같은 형식으로 적어주면 먼저 x [0]을 기준으로 정렬하고 정렬했을 때 동일한 조건에 의해 겹친다면 x [1]을 기준으로 겹치는 애들을 정렬해 준다는 뜻이다.

 

다음은 처음에 제출했던 시간 초과가 난 코드이다.

import sys
input = sys.stdin.readline
n = int(input())
lst = []
for i in range(n):
    lst.append(input().split())
    lst.sort(key = lambda x: (x[0],i))

for result in lst:
    print(" ".join(result))

 

입력을 받으면서 리스트에 넣어준다음 이를 나이순으로 먼저 정렬하고, 입력된 순서를 알아야 하기 때문에 for문에서 i를 기준으로 정렬을 하려고 했다. 이렇게 하면 답은 나오지만 입력이 많아지면 for문을 돌릴 때마다 정렬을 계속해야 해서 시간초과가 발생하는 것 같다. 

 

• 제출코드

import sys
input = sys.stdin.readline
n = int(input())
lst = []
for i in range(n):
    data = input().split()
    lst.append((int(data[0]),i,data))
lst.sort(key = lambda x: (x[0],x[1]))

for result in lst:
    print(" ".join(result[2]))

 

그래서 배열에 저장할 때 나이, 들어온 순서를 모두 저장해주었다. 리스트에 모두 저장한 후 for문을 나와서 정렬을 한 번만 해주었다. 지금 리스트 첫 번째 요소에 나이, 두 번째 요소에 들어온 순서가 저장되어 있으니 정렬할 때 위와 같은 형식으로 key = lambda를 이용하였다. 그리고 마지막에 출력할 때 리스트의 두 번째 요소에 출력 형식에 맞춰 저장해 두어서 바로 두 번째 요소를 출력해 주었다. 

 

이번 문제를 풀면서 key = lambda x를 이용하여 정렬을 해야겠다는 생각을 한 점은 잘한 것 같다. 하지만 for문에서 계속 입력을 받고 받을 때마다 정렬을 해야겠다는 생각을 했을 때 시간초과 관련해서 생각하지 못한 점이 조금 아쉬웠다.