[LeetCode] 147. Insertion Sort List

1. 문제 이해

Linked List를 Insertion Sort를 사용해서 정렬한다.

 

 

2. 풀이 과정

Insertion Sort는 정렬을 해야 할 대상과 정렬을 끝낸 대상, 두 그룹으로 나눠 진행한다.

cur은 정렬을 끝낸 대상, head는 정렬을 해야 할 대상이다.

parent는 cur의 시작 지점을 기억하는 역할을 한다.

cur = parent = ListNode(None)

 

모든 과정은 정렬을 해야 할 대상인 head가 존재하는 경우에 진행한다.

정렬을 끝낸 cur는 head와 비교하면서 더 작다면 cur.next로 이동한다.

삽입할 위치를 찾는 것이다.(cur 바로 다음)

while cur.next and cur.next.val < head.val:
    cur = cur.next

 

삽입한다.

Python의 Multiple Assignment를 활용한다.

오른쪽 값들이 먼저 평가된다. 값들이 임시 저장된다.

왼쪽 변수에 차례대로 할당된다. 기존 값들이 이미 저장되어 있기 때문에 서로 영향을 미치지 않는다.

cur.next, head.next, head = head, cur.next, head.next

 

그리고 cur은 다시 parent로 돌아간다.

cur = parent

 

수행 시간을 줄일 수 있을까?

cur이 무조건 parent로 돌아가야할까?

cur이 head보다 큰 경우에만 돌아가면 된다.

if head and cur.val > head.val:
    cur = parent

 

 

3. 전체 코드

class Solution:
    def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur = parent = ListNode(None)
        while head:
            #삽입할 위치를 찾는다.
            while cur.next and cur.next.val < head.val:
                cur = cur.next
            
            cur.next, head.next, head = head, cur.next, head.next
            cur = parent
            
        return parent.next

 

수행 시간을 줄인 버전이다.(419ms -> 64ms)

class Solution:
    def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur = parent = ListNode(0)
        while head:
            #삽입할 위치를 찾는다.
            while cur.next and cur.next.val < head.val:
                cur = cur.next
            
            cur.next, head.next, head = head, cur.next, head.next
            
            if head and cur.val > head.val:
                cur = parent
            
        return parent.next

 

 

4. 생각할 점

- Multiple Assignment의 진행 과정

- 수행 시간을 줄이기 위한 조건문을 추가하는 발상

 

 

5. 출처

- https://leetcode.com/problems/insertion-sort-list/

- 박상길, 파이썬 알고리즘 인터뷰, 책만, 2020