목차
문제
https://leetcode.com/problems/design-circular-deque/
원형 데크를 디자인하는 문제다.
데크는 double-ended queue의 줄임말로 양쪽에서 삭제, 삽입이 모두 가능한 자료구조다.
예시 입출력
Input
["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
Output
[null, true, true, true, false, 2, true, true, true, 4]
풀이
내 풀이
class MyCircularDeque:
def __init__(self, k: int):
self.k=k
self.a=[]
def insertFront(self, value: int) -> bool:
if not self.isFull():
self.a.insert(0, value)
return True
return False
def insertLast(self, value: int) -> bool:
if not self.isFull():
self.a.append(value)
return True
return False
def deleteFront(self) -> bool:
if not self.isEmpty():
del self.a[0]
return True
return False
def deleteLast(self) -> bool:
if not self.isEmpty():
self.a.pop()
return True
return False
def getFront(self) -> int:
if not self.isEmpty():
return self.a[0]
return -1
def getRear(self) -> int:
if not self.isEmpty():
return self.a[-1]
return -1
def isEmpty(self) -> bool:
if len(self.a)==0:
return True
return False
def isFull(self) -> bool:
if len(self.a)==self.k:
return True
return False
나는 리스트를 사용해서 원형데크를 구현했다. insertFront는 리스트의 insert를 사용하고 insertLast는 append를 사용했다. deleteFront는 del을 사용하고 deleteLast는 pop을 사용했다.
값을 조회하는 건 리스트의 인덱스를 사용했다.
책 풀이
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class MyCircularDeque:
def __init__(self, k: int):
self.head, self.tail = ListNode(None), ListNode(None)
self.k, self.len = k, 0
self.head.right, self.tail.left = self.tail, self.head
# 이중 연결 리스트에 신규 노드 삽입
def _add(self, node: ListNode, new: ListNode):
n = node.right
node.right = new
new.left, new.right = node, n
n.left = new
def _del(self, node: ListNode):
n = node.right.right
node.right = n
n.left = node
def insertFront(self, value: int) -> bool:
if self.len == self.k:
return False
self.len += 1
self._add(self.head, ListNode(value))
return True
def insertLast(self, value: int) -> bool:
if self.len == self.k:
return False
self.len += 1
self._add(self.tail.left, ListNode(value))
return True
def deleteFront(self) -> bool:
if self.len == 0:
return False
self.len -= 1
self._del(self.head)
return True
def deleteLast(self) -> bool:
if self.len == 0:
return False
self.len -= 1
self._del(self.tail.left.left)
return True
def getFront(self) -> int:
return self.head.right.val if self.len else -1
def getRear(self) -> int:
return self.tail.left.val if self.len else -1
def isEmpty(self) -> bool:
return self.len == 0
def isFull(self) -> bool:
return self.len == self.k
책에서는 이중 연결 리스트를 사용해서 구현했다.
원형 데크의 init 부분을 보면 head, tail이 있고 최대 길이, 현재 길이 정보를 저장하는 변수가 있다. 이중 연결 리스트에 신규 노드를 삽입하는 연산(_add)도 따로 추가했다.
그런데 head.right이나 tail.left가 갑자기 선언하지도 않았는데 나오길래 왜 그런건지 의문이 생겼다.
그래서 직접 실험을 해보니까 리스트로 실험해봤을 때는 에러가 나는데 직접 정의한 클래스로 하면 오류가 나지 않는다.
head, tail이 직접 정의한 클래스인 ListNode로 정의되었기 때문에 .right을 해도 상관이 없는 것이다.
책에서 구현한 연산들을 살펴보자.
insertFront()는 head 위치에 노드를 삽입하고 insertLast는 tail.left에 노드를 삽입한다.
del 연산은 인자로 받은 위치의 다음다음 노드를 인자로 받은 노드의 다음으로 연결하는 방식으로 삭제한다. 따라서 deleteFront를 할때는 head를 인자로 넘기지만 deleteLast를 할 때는 tail.left.left를 인자로 넘긴다. 그래야 tail.left.left를 넘겨야 tail.left를 지울 수 있다.
참고한 책 : 파이썬 알고리즘 인터뷰
'Study > Algorithm' 카테고리의 다른 글
[LeetCode] #706. Design HashMap (python) (0) | 2022.03.09 |
---|---|
[LeetCode] #23. Merge k Sorted Lists (python) (0) | 2022.03.09 |
[LeetCode] #622. Design Circular Queue (python) (0) | 2022.03.09 |
[LeetCode] #232. Implement Queue using Stacks (python) (0) | 2022.02.24 |
[LeetCode] #225. Implement Stack using Queues (python) (0) | 2022.02.24 |