[백준/Python]11650: 좌표 정렬하기

문제

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

백준 문제집 - 0x0E강 - 정렬 I

 

알고리즘: 정렬

---

풀이

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

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

 

(x, y)로 구성된 좌표들을 1) x가 증가하는 순으로, 2) 동일하다면 y가 증가하는 순으로 정렬하는 문제다.

 

사실 이 문제는... 단순히 sort()만 사용하면 된다.

(x, y)의 튜플이 있을때 기본적인 정렬 순서는 x 정렬 → y 정렬 이기때문이다.

만약 문제가 "y기준으로 정렬 후 x기준으로 정렬" 이었다면 추가적인 코드가 필요하겠지만, 정렬 기준이 좌표의 인덱스 순서와 동일하므로 별다른 조건이 필요없다.

 

전체 코드

# 메모리: 44580KB / 시간: 260ms
import sys


input = sys.stdin.readline

N = int(input())
points = [tuple(map(int, input().split())) for _ in range(N)]
points.sort()

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

 

만약 인덱스와 다른 순서로 정렬해야한다면,

sort()함수의 key= 인자와 lambda를 사용하면 매우 간단하다!

 

먼저 (x, y) 형태의 튜플들을 인자로 받아온 뒤, 우선순위를 작성해주면 된다.

lambda에서 사용할 변수를 a라고 했을때, a는 각 (x, y) 튜플들을 나타낸다.

첫번째는 x가 증가하는 순(오름차순)이므로 a[0], 두번째는 y가 증가하는 순이므로 a[1]를 순서대로 선택해주면 된다.

단, 정렬 기준을 여러개 작성할경우 괄호()로 꼭 감싸줘야한다.

# 메모리: 51900KB / 시간: 284ms
import sys


input = sys.stdin.readline

N = int(input())
points = [tuple(map(int, input().split())) for _ in range(N)]
points.sort(key=lambda x: (x[0], x[1]))

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

 

그렇다면 lambda를 사용하지 않고 풀려면 어떻게 해야할까?

정렬 기준 값을 따로 저장한 뒤 sort 해주면 된다.

(x, y, z) 형태의 튜플들로 이루어진 리스트가 있다고 가정해보자.

1. x가 증가하는 순

2. 같다면 y가 증가하는 순

3. 같다면 z가 감소하는 순

으로 정렬을 하려면, 기준은 (a[0], a[1], -a[2]) 가 된다.

(위 기준값들, 원래의 값)으로 새로운 리스트를 생성한 뒤 정렬 후 원래의 값만 출력해주면 lambda를 사용한것과 동일하다.

data = [(1, 3, 5), (1, 2, 7), (2, 3, 6), (1, 3, 2)]

# 정렬 기준이 되는 중간 리스트 생성
tmp = [(x[0], x[1], -x[2], x) for x in data]

# 중간 리스트 정렬
tmp.sort()

# 원본 데이터 추출
sorted_data = [item[3] for item in tmp]

print(sorted_data)
# 출력: [(1, 2, 7), (1, 3, 5), (1, 3, 2), (2, 3, 6)]