boj-11650(좌표 정렬하기)

백준 11650번 문제는 아주 간단하였다.
좌표를 오름차순으로 정리하는 문제인데, x의 좌표가 동일하다면, y자표의 대소를 비교하여 순서대로 출력해준다.

처음에는 간단한 알고리즘인, Bubble Sort를 이용해서 정렬을 해보았다.
하지만 역시 간단하게 해결 되지는 않고, 시간 초과가 나왔다.

그래서 이제 그 후로 Merge Sort를 사용하여 해결하였다.

N = [list(map(int, input().split(" "))) for i in range(int(input()))]

def merge(left, right):
    v = list()
    i = 0
    j = 0

    while (i < len(left) and j < len(right)):
        if left[i] <= right[j]:
            v.append(left[i])
            i+=1
        else:
            v.append(right[j])
            j += 1
    
    if i == len(left):
        v = v + right[j:len(right)]
    if j == len(right):
        v = v + left[i:len(left)]
    return v
def merge_sort(a_list):
    if len(a_list) <= 1:
        return a_list
    m = len(a_list) // 2
    left = merge_sort(a_list[0:m])
    right = merge_sort(a_list[m:len(a_list)])

    return merge(left, right)

sort_num = merge_sort(N) # x에 대해서 정렬

for i in range(len(N)):
    print(sort_num[i][0], sort_num[i][1])