[Python]정렬 백준 11651

문제

2차원 평면 위의 점 N개가 주어진다. 좌표를 y좌표가 증가하는 순으로, y좌표가 같으면 x좌표가 증가하는 순서로 정렬한 다음 

출력하는 프로그램을 작성하시오.

입력

첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다.

 (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.

출력

첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다.

이전문제에서 달라진점은 정렬의 우선순위가 y라는 점이다.

이전코드에서 배열의 0 과 1 부분만 바꿔주면 되지만 이전에 구현하지 않았던 병합정렬을 통해 구현해보았다.

import sys
 
 
 
n=int(sys.stdin.readline())
xy_list=[[int(i) for i in sys.stdin.readline().split()] for _ in range(n)]
 
 
#합병정렬
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][1]<right[j][1]:#왼쪽의 y인자가 더작다면 먼저 arr에 추가해준다 같은점이 없다고 나와있지만 넣었다.
            arr.append(left[i])
            i+=1
        elif left[i][1]==right[j][1]:
            if left[i][0]<right[j][0]:#x인자 비교
                arr.append(left[i])
                i+=1
            else:
                arr.append(right[j])
                j+=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
 
 
xy_list=mergeSort(xy_list)
 
for i in range(len(xy_list)):
    print(xy_list[i][0],xy_list[i][1])