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

 

문제 링크

나이순 정렬 : https://www.acmicpc.net/problem/10814

 

 

문제탐색

기본 원리 탐색

• 이 문제는 정수를 기준으로 오름차순 정렬을 수행하는 문제입니다.
• 정렬 시 아래 두 가지 조건을 충족해야 합니다:
  1. 같은 나이일 경우 입력받은 순서를 유지해야 합니다. 
  2. 나이와 이름이 세트로 엮여 있는 구조를 처리해야 합니다.

 

시간복잡도와 알고리즘

• 시간 제한: 3초
  • 3초=> 약 3억 번의 연산을 기준으로 합니다.
• 회원 수 : 최대 100,000
  • 이 경우 시간 복잡도가 O(n²) 인 알고리즘은 약 100억 회 이상의 연산이 필요하므로 불가능합니다.
  • 파이썬의 sorted 함수는 최악의 경우에도  O(n log n) 복잡도를 가지므로 약 500,000회 가 예상됩니다.

=> python의 sorted함수를 사용하여 구현하기로 합니다.

 

 

코드설계하기

• 나이와 이름을 입력받아 2중 리스트 형태로 저장합니다.
• sorted 함수를 사용해 나이를 기준으로 정렬합니다.
• 나이와 이름을 출력합니다.

 

 

시도회차 수정사항

1회차 : sorted함수를 그냥 사용하였더니 동일한 값이 있을 때 첫 번째 기준 요소 외에도 두 번째 요소를 사용하여 정렬을 수행하여 순서가 뒤바뀜. 첫번째 행만 기준으로 사용할 수 있도록 수정.

 

정답코드

n=int(input())

Plist=[]

for x in range(n):
    a,b=input().split() 
    a=int(a) #a는 정수로 변환하여 저장
    Plist.append([a,b])

for x in sorted(Plist, key=lambda x: x[0]): #리스트를 오름차순 정렬 (첫번째 요소(정수)기준)
    print(x[0],x[1]) #출력