백준 11651 - 좌표 정렬하기 2 (파이썬)

Answer

from sys import stdin, stdout

input = stdin.readline

n = int(input())
c = [list(map(int, input().split())) for _ in range(n)]

def quick_sort(a, s, e, i):
    def sort(l, h, i):
        if l >= h:
            return
        
        m = partition(l, h, i)
        sort(l, m - 1, i)
        sort(m, h, i)
        
    def partition(l, h, i):
        p = a[(l + h) // 2][i]
        while l <= h:
            while a[l][i] < p:
                l += 1
            while a[h][i] > p:
                h -= 1
            if l <= h:
                a[l], a[h] = a[h], a[l]
                l, h = l + 1, h - 1
        return l

    return sort(s, e, i)
        
quick_sort(c, 0, n - 1, 1)

s = 1
e = n - 1
t = 0

while s < n - 1:
    p = 1
    for i in range(s, n):
        if c[i - 1][1] != c[i][1]:
            e = i - 1
            t = i + 1
            break
        p += 1
    quick_sort(c, s - 1, e, 0)
    if p == n:
        break
    s = t
    
for i in c:
    stdout.write('{} {}\n'.format(i[0], i[1]))