11650: 좌표 정렬하기 - Python

문제

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

풀이 1-1

import sys
input = sys.stdin.readline

arr = [list(map(int, input().split())) for _ in range(int(input()))]
arr.sort(key=lambda i: i[1])
arr.sort(key=lambda i: i[0]) # 안정 정렬
for i in arr:
    print(*i)

• y좌표(i[1]) 기준으로 정렬 -> x좌표(i[0]) 기준으로 정렬
• .sort() 함수는 안정 정렬(stable sort); 정렬 후에도 같은 key들의 상대적인 순서가 정렬 이전과 같게 유지
  -> 시간 복잡도: 2 * O(N log N)

풀이 1-2

import sys
input = sys.stdin.readline

arr = [list(map(int, input().split())) for _ in range(int(input()))]
arr.sort(key=lambda i: (i[0], i[1]))
for i in arr:
    print(*i)

• .sort()를 한 번만 사용했다.
  -> 시간 복잡도: O(N log N)

풀이 1-1, 1-2 비교

• 풀이 1-1은 두 번의 정렬을 수행하며, 각 정렬은 단일 key(=한 가지 기준)만 사용
  -> 시간 ⬆️, 메모리 ⬇️
• 풀이 1-2는 한 번의 정렬을 수행하며, 정렬 시 복합 key(=두 가지 기준) 사용 + (x, y) 튜플을 생성해 key로 사용
  -> 시간 ⬇️, 메모리 ⬆️

풀이 2

import sys
input = sys.stdin.readline

arr = [list(map(int, input().split())) for _ in range(int(input()))]
arr.sort(key=lambda i: (i[0], i[1]))
print("\n".join(f"{x} {y}" for x, y in arr))

• 풀이 1-2의 출력 부분을 unpacking에서 "\n".join()으로 수정했다.
  -> 시간은 감소했으나 (-40ms) 메모리가 소폭 상승했다(+1000KB).
  -> 출력하기 전 arr의 모든 원소를 문자열에 담는 대규모 할당이 발생해서 그렇다.

풀이 3

import sys
input = sys.stdin.readline

arr = [list(map(int, input().split())) for _ in range(int(input()))]
arr.sort()  
print("\n".join(f"{x} {y}" for x, y in arr))

• 굉충(굉장히 충격적인 사실): 그냥 .sort()만 써도 된다는 것
  -> (x, y) 형태의 tuple이므로 자동으로 x 우선으로 정렬하고, x가 동일하면 y 기준으로 오름차순 정렬한다.
  -> 풀이 2에 비해 메모리가 소폭 감소했다(500KB).

---

교훈

• 시간과 메모리 두 측면에서 생각해보자.
  -> 예시) 여러 줄 출력 시 unpacking은 메모리 측면에서, "\n".join()은 시간 측면에서 유리하다.
• sys.stdout.write는 상황에 맞게 쓰자.
  -> 풀이 3에서 print = sys.stdout.write를 추가하여 제출했더니 시간만 증가했다(+68ms).

참고 자료

• 정렬 안정성 (Stability)