[알고리즘][파이썬] 백준_11651_좌표 정렬하기 2

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

11651번: 좌표 정렬하기 2

x, y 좌표의 점이 N개 있다.

좌표 y를 기준으로 점을 오름차순 정렬해야한다.

이때 y가 동일하면 x로 순서를 결정한다.

 

11650번 좌표 정렬하기 1은 x가 우선이라

sort 함수의 사용만으로 문제를 해결 할 수 있었다.

반면 다소 까다로워진 문제다.

---

시간 초과

# 1차 시도(결과: 시간 초과)
import sys

# xy를 yx로 순서를 바꾸고, 오름차순 정렬 후, yx를 xy로 순서 바꿈
def yx_sort(ipt):
    r_lst = []
    for i in ipt:
        r_lst.append(list(reversed(i)))
        r_lst.sort() # r_lst에 대한 정렬은 for문 밖에서 진행되어야 함

    rst = []
    for i in r_lst:
        rst.append(list(reversed(i)))

    return rst

ipt = []
for _ in range(int(sys.stdin.readline())):
    ipt.append(list(map(int, sys.stdin.readline().split())))

rst = yx_sort(ipt)
for i in rst:
    print(i[0], i[1])

 

리스트 함수 sort 는 기본적으로 다차원 리스트를 정렬할때

앞쪽 주소의 값을 우선하여 정렬한다.

앞 주소의 값이 같으면 그 다음 주소 값을 순차적으로 비교한다.

다차원 리스트 sort 시 비교 우선순위

 

값 x, y는 각각 주소0, 주소1에 위치해 있다.

이번 문제는 y를 1순위로 정렬해야 하기 때문에

sort를 이용해 정렬하기 위해서는

x, y값을 y, x로 바꾼 후 정렬하고

y, x에서 x, y로 다시 바꿔주어야 했다.

이때 내장함수 reversed를 이용했다.

 

1차 시도에서 시간 초과가 발생했다.

코드를 살펴보니

sort가 for문 안 위치해 있었다.

for문을 통해 r_lst가 완성된 후

1회만 정렬하면 되는데,

불필요하게 많은 정렬이 일어난 것이다.

sort 부분을 for문 밖으로 꺼낸 후 제출,

간단히 해결 할 수 있었다!

---

최종 제출 코드

# 2차 시도(결과: 맞았습니다!)
import sys

def yx_sort(ipt):
    r_lst = []
    for i in ipt:
        r_lst.append(list(reversed(i)))
        
    r_lst.sort() # for문 밖으로 꺼냄

    rst = []
    for i in r_lst:
        rst.append(list(reversed(i)))

    return rst

ipt = []
for _ in range(int(sys.stdin.readline())):
    ipt.append(list(map(int, sys.stdin.readline().split())))

rst = yx_sort(ipt)
for i in rst:
    print(i[0], i[1])