질문

import sys
n = int(input())
circles = []
for _ in range(n):
x, r = map(int, sys.stdin.readline().split())
circles.append(("L", x - r))
circles.append(("R", x + r))

circles.sort(key=lambda x: (x[0]),  reverse=True)
circles.sort(key=lambda x: x[1])

이 경우 독립적인 sort를 2번 썼는데, 앞에서 한 정렬의 결과가 보장된다고 하는데 왜 그러는지 설명해 줄 수 있어?

응답

물론입니다! 주어진 코드에서 두 번의 정렬이 어떻게 작동하는지와 왜 두 번째 정렬에서 첫 번째 정렬의 결과가 보장되는지 설명하겠습니다.

코드 분석

import sys
n = int(input())
circles = []
for _ in range(n):
    x, r = map(int, sys.stdin.readline().split())
    circles.append(("L", x - r))
    circles.append(("R", x + r))

circles.sort(key=lambda x: (x[0]),  reverse=True)
circles.sort(key=lambda x: x[1])

1. 두 번의 정렬

1. 첫 번째 정렬:

   circles.sort(key=lambda x: (x[0]), reverse=True)
   
   

   이 정렬은 key에 따라 (x[0])을 기준으로 정렬합니다. 여기서 x[0]은 "L" 또는 "R"이므로, 이 정렬은 ("L", ...)이 ("R", ...)보다 먼저 오도록 만듭니다. 즉, 모든 ("L", ...)이 모든 ("R", ...)보다 앞에 위치합니다.

2. 두 번째 정렬:

   circles.sort(key=lambda x: x[1])
   
   

   이 정렬은 key에 따라 x[1]을 기준으로 오름차순으로 정렬합니다. 즉, 원의 좌표 값 (즉, x - r 또는 x + r)을 기준으로 정렬합니다.

2. 두 번의 정렬이 조화되는 이유

파이썬의 정렬 알고리즘은 안정적(stable) 정렬입니다. 안정 정렬에서는 같은 값이 있을 때, 이전의 정렬 상태가 유지됩니다. 즉, 두 번째 정렬이 첫 번째 정렬의 결과를 유지하면서 진행됩니다.

안정성이란, 같은 키 값이 있을 경우 첫 번째 정렬에서의 순서가 두 번째 정렬에서도 그대로 유지된다는 의미입니다. 예를 들어, ("L", 1)과 ("R", 1)이 있다면, 첫 번째 정렬 후 ("L", 1)은 ("R", 1)보다 앞에 있게 되며, 두 번째 정렬에서 1이라는 값이 같은 경우 원래의 순서 (("L", 1) 먼저) 그대로 유지됩니다.

따라서:

• 첫 번째 정렬에서는 "L"이 "R"보다 앞에 오도록 정렬되고,
• 두 번째 정렬에서는 x[1] 값에 따라 정렬됩니다.

정렬 과정의 결과:

1. 모든 "L" 태그의 원들이 먼저 오고,
2. 같은 x[1] 값이 있는 경우, "L"이 "R"보다 먼저 오게 됩니다.