(Leetcode) 23 - Merge k Sorted Lists
New Year Gift - Curated List of Top 75 LeetCode Questions to Save Your Time
위 링크에 있는 추천 문제들을 시간이 있을때마다 풀어보려고 한다.
https://leetcode.com/problems/merge-k-sorted-lists/description/
이번 문제는 heap으로 푸는 문제이다.
하지만 문제를 딱 보았을 때 sort로도 풀 수 있을것 같은데? 라는 생각이 들어서 두 가지 방법으로 모두 풀어보았다.
heap으로 풀어보기
python 자체적으로 heap 객체를 쓸 수 있게 제공되는것 같다. 하지만 공부를 위해 직접 구현해서 풀었다. 그러다보니 코드가 엄청 길어졌다.
from typing import Optional
from typing import List
import math
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Heap:
def __init__(self):
self.array = []
self.size = 0
def add(self, value: int):
self.array.append(value)
self.size += 1
pointer = self.size
while pointer > 1:
temp_pointer = math.floor(pointer/2)
if self.array[temp_pointer-1] > self.array[pointer-1]:
temp = self.array[temp_pointer-1]
self.array[temp_pointer-1] = self.array[pointer-1]
self.array[pointer-1] = temp
pointer = temp_pointer
else:
break
def pop(self):
if self.size == 0:
return None
if self.size == 1:
self.size -= 1
return self.array.pop()
result = self.array[0]
self.array[0] = self.array.pop()
self.size -= 1
currentIndex = 0
lastIndex = self.size - 1
while True:
leftIndex = currentIndex * 2 + 1
rightIndex = currentIndex * 2 + 2
if lastIndex < leftIndex:
break
elif lastIndex == leftIndex:
if self.array[currentIndex] > self.array[lastIndex]:
temp = self.array[currentIndex]
self.array[currentIndex] = self.array[lastIndex]
self.array[lastIndex] = temp
currentIndex = leftIndex
else:
smallerIndex = leftIndex if self.array[leftIndex] < self.array[rightIndex] else rightIndex
if self.array[currentIndex] > self.array[smallerIndex]:
temp = self.array[currentIndex]
self.array[currentIndex] = self.array[smallerIndex]
self.array[smallerIndex] = temp
currentIndex = smallerIndex
return result
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
if len(lists) == 0:
return None
heap = Heap()
for list in lists:
current = list
while current is not None:
heap.add(current.val)
current = current.next
if heap.size == 0:
return None
result = ListNode(val=heap.pop())
current = result
while heap.size > 0:
current.next = ListNode(val=heap.pop())
current = current.next
return result
quicksort로 풀어보기
마찬가지로 sort를 가져다 쓰면 편했겠지만 직접 quicksort를 구현하여 풀었다.
import json
from typing import Optional
from typing import List
from typing import Optional
from typing import List
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
if len(lists) == 0:
return None
concat = []
for list in lists:
current = list
while current is not None:
concat.append(current.val)
current = current.next
if len(concat) == 0:
return None
else:
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
sorted = quick_sort(concat)
head = ListNode(val=sorted.pop(0))
current = head
for val in sorted:
current.next = ListNode(val=val)
current = current.next
return head
다른 풀이?
이상하게 푸신분들이 있었다.
class Solution:
f = open("user.out", 'w')
print(sys.stdin)
for s in sys.stdin:
print(s)
print('[', ','.join(
map(str, sorted(int(v) for v in s.rstrip().replace('[', ',').replace(']', ',').split(',') if v))), ']', sep='', file=f)
exit()
기타
첫 hard 난이도 문제였다.
300만위 안으로 들어왔다.
