백준 11650번 : 좌표정렬하기(S5)

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

✨  문제

2차원 평면 위의 점 N개가 주어진다. 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.

 

내 코드

import sys
import random

input = sys.stdin.readline

def quick_sort(points):
    if len(points) <= 1:
        return points

    pivot = points[len(points) // 2]
    less = [p for p in points if p[0] < pivot[0] or (p[0] == pivot[0] and p[1] < pivot[1])]
    equal = [p for p in points if p[0] == pivot[0] and p[1] == pivot[1]]
    greater = [p for p in points if p[0] > pivot[0] or (p[0] == pivot[0] and p[1] > pivot[1])]

    return quick_sort(less) + equal + quick_sort(greater)

def main_quick() :
    N = int(input())
    array = []

    for i in range(N) : # 받을 좌표들 모두 array에 저장
        x, y = list(map(int, input().rstrip().split()))
        array.append((x,y))
    array.sort(key=lambda point :(point[0], point[1]))
    sorted_points = quick_sort(array)
    for x, y in array :
        print(x, y)

def main_lambda() :
    N = int(input())
    array = []

    for i in range(N) : # 받을 좌표들 모두 array에 저장
        x, y = list(map(int, input().rstrip().split()))
        array.append((x,y))
    array.sort(key=lambda point :(point[0], point[1]))
    for x, y in array :
        print(x, y)
if __name__ =="__main__" :
    main_quick()

메소드

1. 퀵정렬을 이용하는 방식

2. 내장 매소드 sort의 lambda를 이용하는 방식

결론적으로 말하면 내장 메소드가 훨신 빠르고 좋다. 일반적으로 퀵정렬로 직접 구현해야 빠를 것 같지만 그렇지 않다는 것이다. 그러나 코딩 실력 향상을 위해 퀵정렬로 구현하는 방법도 함께 알아두어야 한다. 고로 두 메소드로 다시 풀어봐야 한다.