.leetcode(148. Sort List)

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

 

 

3. 2022.04.08 시도

• top-down 방식으로 다시 풀어봤다.

 

2. 2022.03.29 시도

소요시간: 30분 이상 소요

// 못 풀었다.

풀이 접근 과정

젤 작은거 찾아서 정렬해보자

 

느낀점

• 젤 작은거 찾아서 정렬했떠니Timeout이 났다.
• Merge Sort (divide and conquer)문제다. 드디어 만났는데 1년이 지나도 익숙하지 않다.
• top-down은 공간을 쓰지만 개념이 굉장히 쉽다.
• botton-up은 공간을 절약하는 대신 알고리즘이 어마무시하게 복잡해진다. 잘라내고 붙이고 그리고 이어가고 이런 작업이 쭉 훑었는데도 익숙하지 않다. 이건 조만간 다시 풀 각이다.

 

---

 

1. 2021.02.07 시도

소요시간: 40분 이상

// 못 풀었다.

풀이 접근 과정

배열로 바꾸면 time: O(nlogN) space: O(n) 일거 같다.
버블 sort 하면 time O(n^2) space: O(n) 일거같다.

divide and conquer로 풀어야할거 같다.
"114. Flatten Binary Tree to Linked List" 링크드 리스트 풀이는 기억이 난다.

 

느낀점

• 결국 두 리스트를 어떻게 머지할것인가가 고민이었다. 핵심은 dummy를 둔다는 것과 mid를 구하는 방식이었다.
• divide and conquer의 일종인 merge sort를 처음으로 구현해보았는데 생각보다 어렵지 않다. 핵심은 1번 즉 리스트를 머지하는 것이니깐 말이다. 그런데 이런 top-down 방식은 공간이 O(logN)만큼 든다. 즉 완벽한 솔루션은 아니다.
• 진짜 답은 bottom-up merge sort로 구현해야한다. 이렇게 풀이가 recursive하게 나와서 callstack으로 공간을 차지하는 경우, 글로벌 변수를 통해서 공간을 constant로 만들 수 있기도 하다.
• Bottom-up의 핵심은 2의 배수 사이즈로 자르고 소팅한다. 2의 배수로 자를때 한번에 다 자르지 않고 현재와 다음것만 우선 자른다음에 머지 소팅하고 그다음 또 사이즈만큼 자르고 소팅하고를 이어나간다. 따라서 log만큼 전체 도는 loop가 있고 그 안에서 n만큼도는 루프가 있어 logN의 속도가 나온다.
• 따라서 현재블록과 다음블록을 구분하는 값들이 잘라내는 부분이 필요하고
• 이 부분을 머지하고
• 그 다음에서 사이즈만큼 잘라내기위한 변수들이 필요하다.
• 또 자를때마다 이어나갈 변수도 필요하다.
• 이러다보니 복잡한데 그래도 공간복잡도 O(1)을 만들 수 있다.

 

 

---

알고리즘 정리노트: .leetcode(알고리즘 문제풀이 접근)

반응형