Week 2-2. [Divide & Conquer] 148. Sort List (Python3)

문제 해결 과정

✍️ 나만의 방식으로 문제 정리하기 (=체계화)

https://leetcode.com/problems/sort-list/?envType=study-plan-v2&envId=top-interview-150 

Sort List - LeetCode

주어진 연결리스트를 오름차순 정렬하여 반환하라.

• 문제에 주어진 함수의 리턴 타입은 Optional[ListNode]이다.
  • 이럴 때는 dummy node를 선언하고 그 dummy node의 next를 반환하면 된다.
• 노드 개수의 범위는 [0, 5*10^4]이다.
• 노드의 값의 범위는 [-10^5, 10^5]이다.

 

🔎 어떤 식으로 접근했는가?

주어진 연결 리스트를 순회하여 요소를 리스트에 담고, 리스트를 정렬한 뒤 다시 노드로 만들어 반환한다.

 

🙈 알고리즘 선택: 입력의 크기를 바탕으로

linear search와 sort를 이용한다. 입력의 최대가 5*10^4

 

📝 의사 코드

lst = []
head가 None이 아닌 동안:
	head.val 값을 lst에 추가한다.
    
lst를 오름차순 정렬한다.

ans = cur = ListNode(-1)
x로 lst의 원소를 순회하면서:
	cur.next = ListNode(x)
    cur = cur.next

 

🎯 구현 코드

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        lst = []
        while head:
            lst.append(head.val)
            head = head.next
        lst.sort()

        # ans: 정렬된 연결 리스트의 시작 부분을 가리키는 포인터
        # cur: 현재 연결 리스트의 끝 부분을 가리키는 포인터
        ans = cur = ListNode(-1) # dummy(-1)로 초기화
        for x in lst:
            cur.next = ListNode(x)
            cur = cur.next

        return ans.next

 

내 코드를 탐구해보기

⏱ 성능 측정 (시간복잡도/공간복잡도)

linear search(O(n))와 sort(O(n log n))를 이용한다. 따라서 전체 코드의 시간 복잡도는 O(n log n)이다.

 

✍️ 성능 회고

1초 제한에서 O(n log n)의 최대 입력은 10^6~10^7이다. 문제에서는 최대 입력이 5*10^4이므로 성능은 괜찮다.

 

다른 사람의 코드를 탐구해보기

🎯 구현 코드

• 제약조건을 고려했을 때 안정적으로 O(nlogn)의 시간을 보장하는 병합정렬을 활용하자.
• 연결리스트는 전체 길이를 알 수 없기 때문에 런너 기법을 활용함세 변수를 만들어, 하나의 변수는 한 칸씩, 다른 변수는 두 칸씩 이동하도록 하면, 두 칸씩 이동한 변수가 리스트 끝에 닿을 때, 한 칸씩 이동한 변수는 중간에 도달할 것
• merge 과정은 만약 두 ListNode가 존재하면 값이 작은 쪽이 l1으로 가게끔 치환하고 l1.next에 대해 재귀호출하여 한쪽 ListNode가 None이 될 때까지 호출한다. 이후 병합된 형태의 ListNode가 반환되면 재귀를 종료한다.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not (head and head.next): return head
    
        # 런너 기법 활용
        half, slow, fast = None, head, head
        while fast and fast.next:
            half, slow, fast = slow, slow.next, fast.next.next # slow는 1칸, fast는 2칸 이동
        half.next = None # 연결리스트 연결 끊기
        
        # 분할 재귀 호출
        l1 = self.sortList(head)
        l2 = self.sortList(slow) # half를 기준으로 끊은 연결리스트의 첫 번째 노드
        
        return self.mergeTwoLists(l1, l2)

    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

 

⏱ 성능 측정 (시간복잡도/공간복잡도)

정렬 연사의 시간복잡도에 의해 결정된다. 정렬 연산의 시간복잡도는 최소 O(n log n)이다.

 

느낀 점

링크드 리스트에서 병합 정렬을 구현하기 아직은 낯설었다. 링크드 리스트에서 값을 꺼내 파이썬 내장함수를 이용해 정렬하는 코드는 간단하지만, 직접 병합 정렬을 구현하는 방법 또한 알아두어야겠다.

 

참고 자료

[알고리즘] Leetcode #148 리스트 정렬 (Python)

LeetCode #148 Sort List