[알고리즘] Leetcode_147_Insertion_Sort_List

Problem

Solve

그림에서 보는 것처럼 삽입정렬 은 정렬된 부분과 정렬되지 않은 부분으로 나누고, 정렬되지 않은 부분의 한 요소씩 정렬된 부분에서 삽입될 위치를 찾아 정렬하는 방식을 말한다. 배열의 첫번째 원소는 정렬된 부분으로 간주하여 두번째 요소를 왼쪽의 정렬된 부분에서 삽입될 위치를 비교하며 찾아 삽입된다. 이렇게 정렬된 부분의 크기는 하나씩 증가하고 반면에 정렬되지 않은 부분의 크기는 하나씩 감소하면서 반복한다.

배열을 이용한다면 다음과 같을 것이다. 기준값 target으로 잡아 정렬된 부분에서 arr[j]과 값을 비교하면서 작을 경우에 위치를 찾아 해당 인덱스에 삽입시켜주는 방법을 배열의 길이만큼 반복한다.

for(int i = 1; i < arr.length ; i++){
    int target = arr[i];
    int j = i-1;
    
    for(j = i-1 ; j >= 0 && target < arr[j]; j--){
      	arr[j+1] = arr[j];
   }
   arr[j] = target;
}

그치만 이 문제는 연결리스트이다.

public ListNode insertionSortList(ListNode head) {
    if (head == null) {
        return head;
    }

    ListNode helper = new ListNode(0); // 정렬된 리스트의 새로운 시작점
    ListNode cur = head; // 삽입될 노드
    ListNode pre = helper; // 삽입할 노드와 삽입 위치 사이의 노드
    ListNode next = null; // 다음에 삽입될 노드

    // 입력 리스트의 끝까지 반복
    while (cur != null) {
        next = cur.next; // 다음 노드 저장

        // 삽입할 위치를 찾을 때까지 이동
        while (pre.next != null && pre.next.val < cur.val) {
            pre = pre.next;
        }

        // pre와 pre.next 사이에 cur 노드를 삽입
        cur.next = pre.next;
        pre.next = cur;

        // 다음 삽입을 위해 변수 초기화
        pre = helper;
        cur = next;
    }

    return helper.next; // 정렬된 리스트 반환
}

사용해야할 변수가 많다.
cur 은 현재 삽입될 노드를(i), prev는 삽입될 노드와 삽입 위치 사이의 노드를(j), dummy는 초기의 prev 값으로 반환할 노드를, next는 다음에 삽입될 노드(정렬되지 않은 부분)를 가리킨다.

예제 1번의 4-2-1-3 연결리스트를 보자.

<Step 1>
1-1. 현재 cur은 4를 가리키고, prev는 dummy 를 가리키며, next는 2를 가리킨다.
1-2. prev.next인 dummy.next는 null이므로 while문을 돌지 않고 prev는 그대로 dummy 를 가리킨다.
1-3. cur인 4는 pre.next에 삽입되어 연결 리스트는 현재 4로 이루어져 있다.(dummy : (0) - 4 - null)
1-4. 변수 초기화를 위해 prev는 다시 dummy 가리킨다.

<Step 2>
2-1. cur은 다음 노드인 2를 가리키고, prev는 dummy를 가리키며, next는 1을 가리킨다.
2-2. prev.next인 dummy.next는 4를 가리키므로, pre는 4로 이동한다. (while문 - dummy : (0) - 4 - null)
2-3. cur인 2는 pre.next에 삽입되어 연결 리스트는 현재 2-4-null로 이루어져 있다. (dummy : (0) - 2 - 4 - null)
2-4. 변수 초기화를 위해 prev는 다시 dummy 가리킨다.

<Step 3>
3-1. cur은 다음 노드인 1을 가리키고, prev는 dummy 가리키며, next는 3을 가리킨다.
3-2. prev.next인 dummy.next는 2를 가리키므로, prev는 2로 이동한다. (dummy : (0) - 2 - 4 - null)
3-3. cur인 1은 prev.next에 삽입되어 연결 리스트는 현재 1-2-4-null로 이루어져 있다. (dummy : (0) - 1 - 2 - 4 - null)
3-4. 변수 초기화를 위해 prev는 다시 dummy 가리킨다.

<Step 4>
4-1. cur은 다음노드이자 마지막 노드인 3을 가리키고, prev는 dummy를 가리키며, next 는 null을 가리킨다.
4-2. prev.next인 dummy.next는 1을 가리키고 1로 이동한다. 그리고 cur.val 가 가리키는 3보다 작은 곳인 2로 이동한다. dummy : (0) - 1 - 2 - 4 - null)
4-3. cur인 3은 prev.next에 삽입되어 연결 리스트는 현재 1-2-3-4-null로 이루어져 있다. (dummy : (0) - 1 - 2 - 3 - 4 - null)
4-4. 변수 초기화를 위해 prev는 다시 dummy 가리킨다.

연결리스트라는 점 때문에 변수를 사용하는 점에 있어서 애를 먹었다. cur, prev, next 그리고 dummy까지...