[Python]정렬 백준 10814

   문제

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

이문제에서 나이가 같으면 가입순 즉 안정 정렬이 필요하다는것을 알수있다.

https://hellowoori.tistory.com/48

정렬의 마지막 문제이기도 하니 각 정렬에대한 특징들을 알필요가 있을거 같아서 찾아

봤다.코드는  stable(안정) 정렬인 병합정렬을 사용하였다.

 

import sys
 
n=int(sys.stdin.readline())
group_list=[]
 
while n>0:
    n-=1
    age,name=sys.stdin.readline().split() #따로받아서 age의 경우 int형으로 바꾸어준다 바꾸지 않을시 문제가생긴다.ex)21,9
    group_list.append([int(age),name])
 
 
######################################################################
#합병정렬
def mergeSort(li):
    if len(li)<=1:
        return li
    mid=len(li)//2
 
    left=li[:mid]
    right=li[mid:]
 
    left1=mergeSort(left)
    right1=mergeSort(right)
 
    return merge(left1,right1)
 
 
def merge(left,right):
    i = 0  # 인자위치
    j = 0
 
    arr = []
 
    while i<len(left) and j<len(right): #왼쪽배열과 오른족 배열이 끝에 닿을때까지
        if left[i][0]<=right[j][0]:#왼쪽의 회원의 나이가 작거나 같다면 (같다면 회원가입순이기때문에)
            arr.append(left[i])
            i+=1
        else:
            arr.append(right[j])
            j+=1
 
    while i<len(left): #위 과정이 끝나고 남은쪽은 차례대로 넣어준다.
        arr.append(left[i])
        i=i+1
    while j<len(right):
        arr.append(right[j])
        j=j+1
 
    return arr
 
 
group_list=mergeSort(group_list)
 
for i in range(len(group_list)):
    print(group_list[i][0],group_list[i][1])