리스트 정렬 ‘

난이도 | ★★ 리트코드 148

문제

Given the head of a linked list, return the list after sorting it in ascending order.

Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?

Example 1:

Input: head = [4,2,1,3]
Output: [1,2,3,4]

Example 2:

Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]

Example 3:

Input: head = []
Output: []

Constraints:

The number of nodes in the list is in the range [0, 5 * 104].
-105 <= Node.val <= 105

[전제]

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:

문제 풀기 전 알고 갈 개념

• =============추가 필요===================

[풀이 1] 파이썬 적합 방식

풀이 1 병합 정렬 코딩 테스트 시 직접 정렬을 구현할 일은 거의 없지만, 이 문제는 연결 리스트를 입력값 으로 주기 때문에 직접 정렬을 구현해야 하는 좋은 문제다. 그러나 시간 복잡도 O(n log n)으로 풀어야 하는 제약사항이 있다. 당연히 버블 정렬 같은 알고리즘은 사용할 수 없으며 연결 리스트 입력에 대해서는 파이썬에서 정렬할 수 있는 별도의 함수를 제공하지 않기 때문에 직접 정렬 알고리즘을 구현해야 한다. 그렇다면 병합 정렬이나 퀵 정렬 정도를 생각할 수 있는데 연결 리스트는 특성상 피벗을 고정된 위치로 지정할 수밖에 없고 입력값에 따라 성능의 편차가 심하므로, 여기서는 우선 병합 정렬로 구현을 시도해보자. 입력값에 따른 성능 편차는 이후 퀵 정렬 풀이에서 다시 자세하게 살펴볼 것이다. 입력값 -1->5->3->4->0 연결 리스트의 병합 정렬 과정을 도식화해보면 그림 17-6과 같다.

그림 17-6 연결 리스트의 병합 정렬 과정 먼저 병합 정렬의 분할 정복 Divide and Conquer 을 위해서는 중앙을 분할 Divide 해야 한다. 이그림에서도 5 를 기준으로 분할하는 과정이 잘 나타나 있다. 그러나 연결 리스트는 전체 길이를 알 수 없기 때문에 여기서는 다음과 같이 런너 Runner 기법을 활용해보자. half, slow, fast = None, head, head while fast and fast.next: half, slow, fast = slow, slow.next, fast.next.next half.next = None half , slow , fast 3개 변수를 만들어 두고 slow 는 한 칸씩, fast 는 두 칸씩 앞으로 이동한 다. 이렇게 하면 fast 가 맨 끝에 도달했을 때 slow 는 중앙에 도착해 있을 것이다. half 는 slow 의 바로 이전 값으로 한다. 그리고 마지막에는 half.next = None 으로 half 위치를 기준으로 연결 리스트 관계를 끊어버린다. 그림 17-6에서는 5 가 half 가 된다. 이제 다음과 같이 분할해서 재귀 호출을 진행해보자. def sortList(self, head: ListNode) -> ListNode: … l1 = self.sortList(head) l2 = self.sortList(slow) head 는 시작 노드이고, slow 는 우리가 탐색을 통해 발견한 중앙 지점이다. 그림 17-6에 서는 3 이 slow 가 된다. 이 값을 기준으로 계속 재귀 호출을 해나가면 결국 연결 리스트는 -1 , 5 , 3 , 4 , 0 단일 아이템으로 모두 쪼개진다. def sortList(self, head: ListNode) -> ListNode: … return self.mergeTwoLists(l1, l2) 이처럼 마지막에는 최종적으로 쪼갰던 아이템을 다시 합쳐서 리턴한다. 그냥 합치는 것이 아니라 다음처럼 크기 비교를 통해 정렬하면서 이어 붙인다. def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode: if l1 and l2: if l1.val > l2.val: l1, l2 = l2, l1 l1.next = self.mergeTwoLists(l1.next, l2) return l1 or l2 mergeTwoLists() 메소드는 연결 리스트를 입력값으로 받아, 길이가 얼마가 되든 재귀 호출을 통해 l1 의 포인터를 이동하면서 정렬해 리턴한다. 여기서 return l1 or l2 는 l1 에값이 있다면 항상 l1 을 리턴하고, l1 이 None 인 경우 l2 를 리턴한다. 즉 l1 이 우선이며, 다음과 같은 간단한 실험을 통해 확인할 수 있다.

1 or None 1 1 or 2 1 None or 2 2 이 부분은 앞서 8장 14번 ‘두 정렬 리스트 병합’ 문제와 동일한 방식으로 풀이가 가능하 다. 그때는 다음과 같은 코드로 풀이했다. def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode: if (not l1) or (l2 and l1.val > l2.val): l1, l2 = l2, l1 if l1: l1.next = self.mergeTwoLists(l1.next, l2) return l1 굳이 l1 or l2 를 비교하지 않고 l1 이 None 이라면 미리 스왑해버리는 방식인데, 어떤 식으로 풀이하든 결과는 동일하다. 둘 중 아무거나 마음에 드는 구현을 택하면 된다. 그렇

다면 과연 이 함수가 잘 동작하는지, 최종적으로 비교가 진행될 -1->5 와 0->3->4 의 마지막 정렬 부분을 그림으로 나타내 자세히 살펴보자. 그림 17-7 병합 정렬 구현의 최종 비교 단계 코드에서 처음에는 l1 에 -1 , l2 에는 0 이 입력값으로 들어오고, l1 의 next 인 5 는 0 보다 크기 때문에 스왑한다. 이후에는 스왑 없이 계속 next 순서로 3 , 4 로 연결된다. 마지막에는 4 의 next 가 None 이고, 이 경우 return l1 or l2 부분에서 l2 값이 리턴되며, 즉 5 가 리턴 된다. 그림 17-7과 같은 순서로 진행이 되며, 재귀 호출된 부분들을 거슬러서 풀어보면 -1->0->3->4->5 . 최종 정렬이 잘 진행됐음을 확인할 수 있다. 이제 전체 코드는 다음과 같이 깔끔하게 정리할 수 있다.

두 정렬 리스트 병합 def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:

if l1 and l2: if l1.val > l2.val: l1, l2 = l2, l1 l1.next = self.mergeTwoLists(l1.next, l2) return l1 or l2 def sortList(self, head: ListNode) -> ListNode: if not (head and return head

런너 기법 활용 half, slow, fast = None, head, head while fast and fast.next:

half, slow, fast = slow, slow.next, fast.next.next half.next = None

분할 재귀 호출 l1 = self.sortList(head) l2 = self.sortList(slow)

return self.mergeTwoLists(l1, l2) 이 풀이는 320밀리초가 걸려, 나쁘지 않은 실행 시간 속도를 보인다. 풀이 2 퀵 정렬 그렇다면 이 문제를 퀵 정렬로 풀 수 있을까? 그리고 더 빨리 풀 수 있을까? 당연히 퀵정렬로 풀 수는 있다. 그러나 이 문제를 로무토 파티션 등의 일반적인 퀵 정렬 알고리즘 으로 구현하면, 타임아웃이 발생해 풀이가 불가능하다. 퀵 정렬을 변형해 좀 더 최적화를 진행해야 풀이가 가능하다. 하지만, 해당 풀이는 이 책의 범위를 벗어나므로 여기서는 설명하지 않는다. 직접 퀵 정렬을 그대로 구현해 테스트해본 결과, 파이썬에서는 타임아웃이 나며 풀이가 불가능했다. 같은 알고리즘으로 자바와 C++는 풀이가 가능했으나, 병합 정렬보다 한참더 오래 걸렸다. 겨우 풀이가 가능한 정도였다. 문제가 발생하는 입력값은 다음과 같은 경우였다.

1,000개 입력값 [1,3,3,1,3,1,3,3,2,3,2,2,1,1,1,3,2,2,1,1,2,2,2,3,3,1,1,2, 1,2,1,3,3,2,2,1,3,1,3,1,3, … ,3,1,2,2,2,1,3,3,3,2,3,1, 1,2,3,3,3,1,3,3,1,2,3,1,3,1,3,2,1,1,3,3,3,2,2,3,3]

head.next): 이렇게 1 , 2 , 3 , 단 3개의 아이템으로 구성된 1,000개 입력값으로 이뤄진 테스트 케이스가 있는데, 이 부분에서 파이썬의 퀵 정렬은 계속 타임아웃을 발생했다. 퀵 정렬은 대표 적인 불안정 정렬로, 같은 값이 반복될 경우에도 계속해서 스왑을 시도한다. 연결 리스트는 특성상 피벗을 임의로 지정하기가 어렵기 때문에 여기서는 피벗을 항상 첫 번째 값으로 설정했는데, 이 경우 이미 정렬된 리스트가 입력값으로 들어오게 되면 계속해서 불균형 리스트로 나뉘기 때문에 그림 17-8의 2)와 같은 최악의 결과를 보일 수 있다. 그림 17-8 퀵 정렬의 1)최선과 2)최악의 경우 11 이러한 문제는 이미 퀵 정렬을 소개할 때 충분히 언급한 바 있다. 이처럼 퀵 정렬은 입력 값에 따라 성능의 편차가 크고 다루기가 까다롭기 때문에, 성능이 우수함에도 실무에서는 좀처럼 퀵 정렬을 사용하지 않는 이유이기도 하다. 이 문제 또한 퀵 정렬로 풀이하기가 어렵다. 특히 동일한 방식으로 자바나 C++로 풀었을 때는 통과했지만, 파이썬은 계속 해서 통과하지 못했다. 리트코드를 비롯한 여타 코딩 테스트 플랫폼들의 타임아웃 설정의 조금 아쉬운 부분이기도 하다(동일 알고리즘으로 풀면 C++로는 풀이가 되는데, 파이썬에 서는 타임아웃이 발생한다). 그렇다면 이 문제를 시간 내에 통과할 수 있는 또 다른 방법은 없을까? 풀이 3 내장 함수를 이용하는 실용적인 방법 사실 이 문제는 정렬 알고리즘을 직접 구현할 필요가 없다. 요즘 대부분의 프로그래밍 언어들은 표준 라이브러리에서 이미 성능 좋은 정렬 알고리즘을 제공하고 있기 때문이다. 앞서 봤듯이 파이썬에서도 .sort() 와 sorted() 를 통해 효율적인 정렬 알고리즘을 제공 하고 있다. 팀소트 Timsort 를 사용한다는 점 또한 이미 살펴본 바 있다. 그렇다면 기본 라 def sortList(self, head: ListNode) -> ListNode:

연결 리스트 -> 파이썬 리스트 p = head lst: List = [] while p:

lst.append(p.val) p = p.next

정렬 lst.sort()

파이썬 리스트 -> 연결 리스트 p = head for i in range(len(lst)):

p.val = lst[i] p = p.next return head 놀랍게도 이 풀이는 84밀리초에 풀린다. 무엇보다 단순하면서도, 직관적이고, 쉽다. 더놀라운 점은 연결 리스트를 리스트로 변경하는 과정이 추가됐음에도 이 방식이 가장 빠르다는 점이다. 이처럼 실무에서나 코딩 테스트 시에 내장 함수를 잘 활용하면 매우 효율 적이기 때문에, 별도의 제약 사항이 없다면 현명하게 활용할 필요가 있다. 풀이 방식 실행 시간 1 병합 정렬 320밀리초 2 퀵 정렬 타임아웃 3 내장 함수를 이용하는 실용적인 방법 84밀리초