[백준,Python]11651번 좌표 정렬하기 2(Sort)

처음 문제를 풀 때, 
생각 없이 아래와 같이 Bubble Sort로 접근하였다. 

import sys
input = sys.stdin.readline

num = int(input())
s_list = []
for i in range(num):
    N,M = map(int, input().split())
    s_list.append([N,M])
c = 0

    


while c <= len(s_list)-1:
    for j in range(len(s_list)-c):
        if s_list[c][1] > s_list[c+j][1]:
            s_list[c], s_list[c+j] = s_list[c+j], s_list[c]
    c += 1

for k in s_list:
    print(k)

하지만 Bubble Sort 방식으로 접근하면 O(n^2) 시간 복잡도를 가진다. 

문제에서 점의 개수(N)이 최대 100,000이라고 주어졌으므로, 이 경우 최악의 시간 복잡도는 대략 100,000^2 = 10,000,000,000 (10억)번 연산이 필요하다. 
일반적인 python 환경에서의 연산속도는 대략 20,000,000(2천만)번이라 가정하면, 50초의 시간이 걸리기 때문에 시간 초과가 나는 것이 당연하다. 

따라서 시간 내에 문제를 해결하기 위해서는 O(NlogN) 의 알고리즘으로 접근해야만 한다.
파이썬 기본 내장 함수의 Timsort 알고리즘( O(NlogN) ) 을 사용하는 sort() 를 사용하여 아래와 같이 구현하였다. 
1. x,y를 교차해서 Append  후 정렬 방법

# Solution_1
import sys
input = sys.stdin.readline

num = int(input())
s_list = []
for i in range(num):
    [N,M] = map(int, input().split())
    s_list.append([M,N])
s_list.sort()


for k in s_list:
    print(k[1],k[0])

또 다른 방법으로는 sort 함수에서 키 값을 y축으로 직접 정하는 방식이다.(lambda 사용)
2. sort의 key을 lambda를 사용하여 y축으로 지정 방법

# Solution_2
import sys
input = sys.stdin.readline

num = int(input())
s_list = []
for i in range(num):
    (x,y) = map(int, input().split())
    s_list.append((x,y))
s_list.sort(key = lambda x: (x[1],x[0]))


for k in s_list:
    print(k[0], k[1])