Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- 코드워
- 프로그래머스
- go
- boj
- docker
- zookeeper
- scala
- DP
- gradle
- OOM
- 주키퍼
- 스칼라
- HBase
- redis
- 파이썬
- 튜토리얼
- leetcode
- 리눅스
- golang
- codewars
- 문제풀이
- Linux
- Python
- programmers
- Go언어
- 자바
- dynamic programming
- 알고리즘
- 동적프로그래밍
- Java
Archives
- Today
- Total
목록2020/06/30 (1)
파이문
148. Sort List
문제 설명 링크드 리스트가 주어지는데, 상수의 공간 복잡도와 O(nlogn) 의 시간 복잡도로 정렬하는 문제다. 코드는 여기서 확인 가능하다. 솔루션 꼼수 가장 쉬운 방법은 링크드 리스트를 배열로 만들어서 언어에 built-in 된 sort 함수를 사용하는 것이다. 참고로 python 은 timsort 라는 알고리즘으로 sort 가 구현되어 있다. 아니면 sort 함수 말고 직접 정렬을 구현하면 될 것 같다. 하지만 이러면 constant space complexity 를 만족할 수가 없다. 두뇌 풀가동 merge sort 로 하면 될 것 같았다. 이때 절반을 divide 해야 하는데 배열이랑 다르게 사이즈를 알 수가 없다. 이를 위해 fast-slow 로 노드를 순회한다. 이는 tortoise-hare..
문제 풀이/leetcode
2020. 6. 30. 22:50