파이썬 / BOJ / 11651 (좌표 정렬하기 2)

문제

 

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

11651번: 좌표 정렬하기 2

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

 

입력

 

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

 

출력

 

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

예제 입출력

예제 입력	예제 출력
5 0 4 1 2 1 -1 2 2 3 3	1 -1 1 2 2 2 3 3 0 4

 

 

풀이

 

처음 푼 방법

 

import sys

N = int(sys.stdin.readline())
num_list = []

for _ in range(N):
    x, y = map(int, sys.stdin.readline().split())
    num_list.append([x,y])
    
result = sorted(num_list, key = lambda number : number[1]) 

for x, y in result :
    print(x, y)
    

문제를 처음 접했을 때 sorted 함수를 이용해서 key값을 들어오는 입력 값의 2번째로 (ex.  0, 4로 들어오면 4) 잡아서 정렬하면 되겠다고 생각했다. 하지만 함수의 대해 정확한 이해가 없었기 때문에 쉬운 문제임에도 계속 틀렸다. 결국 sorted 함수에 대한 정의를 다시 읽었고 위와 같이 풀면 해당 키값을 정렬하고 같은 키값의 경우 처음 들어온 순서를 그대로 유지한다는 것을 알았다. ( ex.  0, 4 / -1, 4 들어오면 -1, 4/ 0, 4 이렇게 정렬되는 것이 아닌 키값이 같으므로 들어온 순서 유지). 그래서 sorted의 다중 key 정렬을 찾은 결과 다음과 같이 괄호를 이용하여서 해줬더니 제출한 코드가 정답으로 처리됐다. 예전에 이 문제에 있어서 itemgetter라는 모듈을 사용한 적이 있는데, 이는 sorted 보다 훨씬 더 속도가 느리게 나왔다.

 

다시 맞게 푼 방법 (sorted로 푼 코드)

import sys

N = int(sys.stdin.readline())
num_list = []

for _ in range(N):
    x, y = map(int, sys.stdin.readline().split())
    num_list.append([x,y])

result = sorted(num_list, key = lambda number : (number[1], number[0]))

for x, y in result :
    print(x, y)

 

 

다시 맞게 푼 방법 (itemgetter로 푼 코드)

 

itemgetter(1,0) --> 1 인덱스에 있는 걸 먼저 정렬하고 그 다음 0 인덱스에 있는 걸 정렬한다는 의미이다.

from operator import itemgetter

num = int(input())
unsorted = []
for _ in range(num):
    x,y = map(int,input().split())
    unsorted.append((x,y))
    
unsorted = sorted(unsorted, key=itemgetter(1,0))

for i in range(num):
    print(unsorted[i][0],unsorted[i][1])