일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
- 문제풀이
- codewars
- 주키퍼
- gradle
- dynamic programming
- Go언어
- Java
- Python
- zookeeper
- 자바
- 튜토리얼
- 코드워
- scala
- 프로그래머스
- 파이썬
- 알고리즘
- programmers
- Linux
- go
- 리눅스
- 동적프로그래밍
- docker
- DP
- golang
- redis
- boj
- HBase
- OOM
- leetcode
- 스칼라
- Today
- Total
파이문
148. Sort List 본문
문제 설명
링크드 리스트가 주어지는데, 상수의 공간 복잡도와 O(nlogn) 의 시간 복잡도로 정렬하는 문제다. 코드는 여기서 확인 가능하다.
솔루션
꼼수
가장 쉬운 방법은 링크드 리스트를 배열로 만들어서 언어에 built-in 된 sort 함수를 사용하는 것이다.
참고로 python 은 timsort 라는 알고리즘으로 sort 가 구현되어 있다.
아니면 sort 함수 말고 직접 정렬을 구현하면 될 것 같다.
하지만 이러면 constant space complexity
를 만족할 수가 없다.
두뇌 풀가동
merge sort 로 하면 될 것 같았다. 이때 절반을 divide 해야 하는데 배열이랑 다르게 사이즈를 알 수가 없다. 이를 위해 fast-slow 로 노드를 순회한다.
이는 tortoise-hare 랑 비슷한데, fast 노드는 두칸씩 가고 slow 노드는 한칸씩 간다. fast 가 끝에 다다르면 slow 는 전체 링크드 리스트의 중간 노드를 가리키고 있을 것이다.
그럼 head ~ slow
, slow ~ 어떤 노드
로 나누면 된다, 이를 각각 명칭을 알기 쉽게 변경하자면 start ~ middle
, middle ~ end
이다.
다만 배열과 다르게 링크드 리스트는 middle
노드의 다음 번째 리스트가 쭉 이어져있기 때문에 그냥 돌리면 같은 것들을 계속 확인하게 된다.
말이 조금 어려워서 다시 정리하자면 아래와 같다.
3 -> 1 -> 2 -> 4
위와 같은 링크드 리스트에서 divide 가 이루어지면 3 -> 1
, 2 -> 4
로 딱 나누어 떨어져야 하는데, 실제로 첫번쨰 리스트는 3 -> 1 -> (2 -> 4)
이렇게 되어 있다는 것이다.
이미 2 -> 4
는 나누어져서 다른 곳에서 어쩌고 저쩌고 할텐데, 이러면 cycle 이 되서 값이 제대로 나오지 않는다.
이를 위해 start -> middle
에서 middle
의 다음 리스트를 잘라주는 작업을 한다. 이렇게 모든 리스트를 잘라주었다면, 다음은 merge
작업을 진행해준다.
merge
작업은 두개의 노드의 값을 비교하는데, 각각을 left
, right
라고 한다면 right
가 left
보다 작으면 두개를 서로 바꿔준다. 서로 바꿔주는 작업도 역시 글은 어려우니 그림으로 보자.
아래와 같이 링크드 리스트가 있다고 할 때, 현재 left
와 right
가 아래와 같다고 해보자
left
1 -> 3
right
2 -> 5
(노드 개수가 2인 이유는 이미 divide 가 되었기 때문이고, merge 의 첫 과정이라고 생각하기 위해서이다.)
left
의 값이 1이고 right
의 값이 2 이다. 이는 정렬 되어 있으므로 left
를 next
로 이동해주자
left
3
right
2 -> 5
여기서는 정렬 되어 있지 않는다. 이럴 경우 right
의 next
와 비교한다.
left
3
right
5
left
보다 right
가 크니까 이대로 merge
한다. 그러면 3 -> 5
가 된다. 이제 거꾸로 가면 된다. 값이 작은 쪽으로 next
하여 비교 하였기 때문에 순서대로 right.next
와 left.next
로 올라가면서 붙여주면 된다. 정리하면 이렇게 될 것이다.
(1)
left
1 -> 3
right
2 -> 5
(2)
left.next 로 이동
left
3
right
2 -> 5
(3)
right.next 로 이동
left
3
right
5
(4)
merge
3 -> 5
(5)
2 -> 3 -> 5 (right: 2, back, right.next 로 붙여준다.)
(6)
1 -> 2 -> 3 -> 5 (left: 1, back, left.next 로 붙여준다.)
전체 코드로 보면 아래와 같다.
class Solution:
def sortList(self, head: ListNode) -> ListNode:
if head is None or head.next is None:
return head
middle = head
fast = head.next
slow = head.next
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
middle = middle.next
middle.next = None
node1 = self.sortList(head)
node2 = self.sortList(slow)
return self.merge(node1, node2)
def merge(self, left, right):
print(left, right)
if left is None:
return right
if right is None:
return left
if left.val < right.val:
left.next = self.merge(left.next, right)
return left
else:
right.next = self.merge(left, right.next)
return right
'문제 풀이 > leetcode' 카테고리의 다른 글
706. Design HashMap (3) | 2020.06.29 |
---|---|
207. Course Schedule (0) | 2019.08.18 |
3. Longest Substring Without Repeating Characters (0) | 2019.07.08 |
2. Add Two Numbers (0) | 2019.06.16 |
518. Coin Change 2 (0) | 2017.04.09 |