Deque
일반적인 연결 리스트는 리스트의 마지막에서 노드를 연결시켜 추가하거나 마지막 노드를 삭제한다. Deque는 head와 tail을 통해 연결 리스트의 앞, 뒤로 노드를 추가하고 삭제할 수 있는 자료구조이다.
Heap
최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리
파이썬에서는 heapq 모듈을 이용하여 heap을 구성할 수 있다. heapq 모듈은 기본적으로 Min Heap을 구성하도록 한다.
- heapq.heappush(heap: list, val: any) : heap에 val을 push하여 heap을 구성한다
- heapq.heappop(heap: list) : heap에서 가장 작은 원소를 빼내어 return
- heapq.heapify(heap: list) : 이미 생성한 리스트를 heapify를 통해 heap으로 만들어줌
- heapq.heappush(heap: list, val: tuple) : heap의 요소로 tuple을 넣을 수 있다. 이 경우 구현에 따라 Max Heap이나 Priority Queue를 구현할 수 있게 된다.
Leetcode 641. Design Circular Deque
원형 Deque를 구현하는 문제이다. 주어진 함수를 구현하여 원형 Deque가 동작하도록 하면 된다.
풀이
InsertFront 예시, InsertLast도 같은 방법으로
DeleteFront 예시, DeleteLast도 같은 방법으로
코드
class Node:
def __init__(self, value, right_node=None, left_node=None):
self.value = value
self.left = right_node
self.right = left_node
class MyCircularDeque:
def __init__(self, k: int):
self.head, self.tail = Node(None), Node(None)
self.max_size = k
self.cur_size = 0
self.head.right = self.tail
self.tail.left = self.head
def insertFront(self, value: int) -> bool:
if not self.isFull():
new_node = Node(value)
head_next = self.head.right
self.head.right, head_next.left = new_node, new_node
new_node.left, new_node.right = self.head, head_next
self.cur_size += 1
return True
return False
def insertLast(self, value: int) -> bool:
if not self.isFull():
new_node = Node(value)
tail_before = self.tail.left
self.tail.left, tail_before.right = new_node, new_node
new_node.left, new_node.right = tail_before, self.tail
self.cur_size += 1
return True
return False
def deleteFront(self) -> bool:
if not self.isEmpty():
head_right = self.head.right.right
head_right.left, self.head.right = self.head, head_right
self.cur_size -= 1
return True
return False
def deleteLast(self) -> bool:
if not self.isEmpty():
tail_before = self.tail.left.left
tail_before.right, self.tail.left = self.tail, tail_before
self.cur_size -= 1
return True
return False
def getFront(self) -> int:
if self.isEmpty():
return -1
return self.head.right.value
def getRear(self) -> int:
if self.isEmpty():
return -1
return self.tail.left.value
def isEmpty(self) -> bool:
return self.cur_size == 0
def isFull(self) -> bool:
return self.cur_size == self.max_sizeLeetcode 23. Merge k Sorted Lists
연결리스트로 이루어진 배열을 받고, 모든 노드들이 정렬되어 있는 연결 리스트를 반환하는 문제이다.
lists = [ 1 → 4 → 5, 1 → 3, 2 → 4 ] 이면 1 → 1 → 2 → 3 → 4 → 4 → 5 를 반환한다.
풀이 1
- data 리스트에 lists의 모든 노드의 값을 저장한다
- data 리스트를 sort한다
- 빈 노드 result를 만든다
- data의 원소를 val로 가지는 노드를 result에 연결시킨다
- result.next를 반환한다
코드
# 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]:
data = []
for li in lists:
cur = li
while cur:
data.append(cur.val)
cur = cur.next
data.sort()
result_root = result = ListNode()
while data:
node = ListNode(data.pop(0))
result.next = node
result = result.next
return result_root.next풀이 2
heapq 모듈을 이용한다.
- lists는 연결리스트의 배열이다. 즉 lists[i]는 연결리스트의 root 노드이다. 튜플을 (root의 val, index i, root)로 만들어 heap에 집어넣는다. 그렇게 되면 root의 val가 작은 순서로 heap이 구성된다.
- heappop으로 root의 val이 가장 작은 연결리스트 하나를 꺼낸다.
- result.next를 뽑아낸 연결리스트로 놓는다.
- 이를 반복하여 heap에 같은 형식으로 넣는다.
- heap이 없어질때까지 반복하면 정렬된 리스트가 나온다.
코드
# Definition for singly-linked 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]:
root = result = ListNode(None)
heap = []
for i in range(len(lists)):
if lists[i]:
heapq.heappush(heap, (lists[i].val, i, lists[i]))
while heap:
node = heapq.heappop(heap)
idx = node[1]
result.next = node[2]
result = result.next
if result.next:
heapq.heappush(heap, (result.next.val, idx, result.next))
return root.nextLeetcode 706. Design HashMap
다음의 기능을 제공하는 해시맵을 디자인하라
- put(key, value): 키, 값을 해시맵에 삽입한다. 이미 존재하는 키라면 업데이트한다.
- get(key): 키에 해당하는 값을 조회한다. 키가 존재하지 않는다면 -1을 반환한다.
- remove(key): 키에 해당하는 키, 값을 해시맵에서 삭제한다.
example)
MyHashMap myHashMap = new MyHashMap();
myHashMap.put(1, 1); // The map is now [[1,1]]
myHashMap.put(2, 2); // The map is now [[1,1], [2,2]]
myHashMap.get(1); // return 1, The map is now [[1,1], [2,2]]
myHashMap.get(3); // return -1 (i.e., not found), The map is now [[1,1], [2,2]]
myHashMap.put(2, 1); // The map is now [[1,1], [2,1]] (i.e., update the existing value)
myHashMap.get(2); // return 1, The map is now [[1,1], [2,1]]
myHashMap.remove(2); // remove the mapping for 2, The map is now [[1,1]]
myHashMap.get(2); // return -1 (i.e., not found), The map is now [[1,1]]
풀이
key와 value를 가지는 ListNode를 이용한다.
코드
class ListNode:
def __init__(self, key = None, value = None):
self.key = key
self.value = value
self.next = None
class MyHashMap:
def __init__(self):
self.size = 1000
self.table = collections.defaultdict(ListNode)
def put(self, key: int, value: int) -> None:
index = key % self.size
if self.table[index].value is None:
self.table[index] = ListNode(key, value)
return
p = self.table[index]
while p:
if p.key == key:
p.value = value
return
if p.next is None:
break
p = p.next
p.next = ListNode(key, value)
def get(self, key: int) -> int:
index = key % self.size
if self.table[index].value is None:
return -1
p = self.table[index]
while p:
if p.key == key:
return p.value
p = p.next
return -1
def remove(self, key: int) -> None:
index = key % self.size
if self.table[index].value is None:
return
p = self.table[index]
if p.key == key:
self.table[index] = ListNode() if p.next is None else p.next
return
prev = p
while p:
if p.key == key:
prev.next = p.next
return
prev, p = p, p.next
# Your MyHashMap object will be instantiated and called as such:
# obj = MyHashMap()
# obj.put(key,value)
# param_2 = obj.get(key)
# obj.remove(key)