[백준 문제풀이] 11651 - 좌표 정렬하기 2

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

문제

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

입력

첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.

출력

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

풀이

11650번 문제와 별 다를게 없다. 바뀐 점이라고는 y좌표를 먼저, x좌표를 먼저라는 것인데 아래 설명했듯이 lambda의 첫 번째 정렬조건을 x[1]로, 두 번째 정렬 조건을 x[0]으로만 바꿔주면 쉽게 통과할 수 있다.

파이썬의 sort() 함수는 기본적으로 Tim sort(팀 정렬)라는 Merge sort(병합 정렬)을 기반으로 삽입 정렬의 아이디어를 섞은 조금 더 효율적인 방법의 정렬을 사용한다. 시간복잡도도 O(NlogN)으로 나쁘지 않기 때문에 문제풀이에 사용하는데 나쁘지 않다. 하지만 메모리 제한이 걸려있는 문제에서는 Tim sort는 메모리를 Merge sort와 같이 많이 잡아먹으므로 주의해야한다.

sort()함수는 기본적으로 오름차순 정렬을 하며, 가장 앞 원소부터 비교해 정렬한다. 그리고 lambda식을 이용하면 2차원 배열또한 정렬해줄 수 있다. 아래 코드에서는 x[0]기준으로 오름차순 정렬을 하고, 뒤에 x[1]을 기준으로 다시 정렬해준다. 이 때 내림차순으로 정렬해주고싶다면 -x[1]같이 마이너스 기호를 붙여주면 된다.

import sys

input = sys.stdin.readline
print = sys.stdout.write

N = int(input())

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

coordinates.sort(key=lambda x: (x[1], x[0]))

for i in range(N):
    answer = str(coordinates[i][0]) + " " + str(coordinates[i][1]) + "\n"
    print("".join(answer))