60. Insertion Sort List

🎯 leetcode - 147. Insertion Sort List

---

📌 문제

- 파이썬 알고리즘 인터뷰 60번 문제
- 연결리스트를 "삽입 정렬"을 사용해 정렬하라.

📌 날짜

2020.02.26

📌 시도 횟수

책 보고 이해함ㅠ / Failed

💡 Code

class Solution:
    def insertionSortList(self, head: ListNode) -> 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
	    cur = parent # 다시 cur을 맨 앞으로 이동
        
        return parent.next

💡 문제 해결 방법

• 문제 해결 과정은 아래와 같다.
  

- cur은 정렬이 완료된 연결 리스트를 가리킨다.
- parent는 "항상" 정렬이 완료된 연결리스트의 루트를 가리킨다.
- head는 정렬을 해야 될 현재 노드를 가리킨다.

1. 정렬되어야 할 현재 노드는 head이다.
2. 이미 정렬된 연결 리스트(cur)에 head가 어디 들어가야 할 지 찾아야 한다.
3. cur은 정렬된 연결리스트를 맨 앞부터 차례대로 순회하면서
cur.next가 head보다 값이 커지는 경우에서 스톱한다.
4. 만약 cur.next.val > head.val인 경우를 찾으면,
> cur.next, head.next, head = head, cur.next, head.next
를 통해 head를 정렬된 연결리스트에 삽입하고 head를 새로운 head로 갱신한다.
⭐반드시 *다중할당*으로 처리해야 된다. 그렇지 않으면 recursion error가 뜸⭐
5. cur을 다시 정렬된 연결리스트 맨 앞으로 옮기고 1~5를 반복한다.

💡 새롭게 알게 된 점

> cur.next, head.next, head = head, cur.next, head.next
다중할당으로 처리해야 recursion error이 뜨지 않음을 알게 되었다.
가독성이 떨어지지만 다중할당으로 처리하는 이유가 있었다. (p.211 참고)

• 삽입 정렬을 까먹었다면 이전 게시물을 다시 보자.
• 삽입 정렬 다시 보기🎈

❌ (한번에 맞추지 못한 경우) 오답의 원인

✔ 더 생각할 점
- 원래 삽입 정렬은 현재 값에 대하여 현재 값의 왼쪽 값인 (가장 큰값)부터 시작하여
차례대로 (큰 값 -> 작은 값) 왼쪽 방향으로 내려가며 삽입 위치를 찾는다.
- 그러나, 연결리스트의 경우 무조건 순차적으로 순회해야 하기 때문에 
큰값에서 작은값으로 거꾸로 거슬러 내려가는 것이 사실상 불가능하다.
- 그렇다면 어떻게 기존 삽입 정렬만큼의 효율을 낼 수 있을까?

---

😉 다른 풀이

📌 하나. 위의 풀이의 비효율성을 고친 풀이

class Solution:
    def insertionSortList(self, head: ListNode) -> 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

            # 만약 새로운 head보다 cur 값이 작다면, cur을 굳이 갱신하지 않고 이전 상태에서 부터 검사할 수 있음
            # 왜냐하면 어차피 위의 경우, cur 이전 값은 cur보다 작기 때문에 조사할 필요가 없음
            if head and cur.val > head.val:
                cur = parent
        return parent.next

💡 문제 해결 방법

- cur의 갱신을 꼭 필요한 경우에만 실행시킴으로써 불필요한 연산을 최소화했다.
- cur.val이 새롭게 삽입해야할 head의 head.val보다 값이 작은 경우
굳이 cur을 맨 앞(가장 작은 값)으로 갱신할 필요가 없다.
- 우리가 찾고자 하는 것은 cur이 언제 "처음" head.val보다 값이 "커지느냐"이기 때문이다.

💡 새롭게 알게 된 점

- 코드의 비효율성을 줄이는 방법을 고려해볼 수 있었다.