반응형
문제
https://leetcode.com/problems/design-circular-queue/
Design Circular Queue - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
원형 큐를 디자인하는 문제다.
원형 큐란?
기존의 큐와 같은 구조를 갖지지만 마지막 위치와 시작 위치가 연결되기 때문에 원형 큐라고 부른다.
기존 큐는 deQueue로 공간이 생겨도 해당 공간을 다시 사용할 수 없었는데 원형 큐는 해당 공간을 재활용할 수 있다.
예시 입출력
Input
["MyCircularQueue", "enQueue", "enQueue", "enQueue", "enQueue", "Rear", "isFull", "deQueue", "enQueue", "Rear"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
Output
[null, true, true, true, false, 3, true, true, true, 4]
풀이
내 풀이
class MyCircularQueue:
def __init__(self, k: int):
self.q=[-1]*(k+1)
self.rear=0
self.front=0
self.k=k+1
def enQueue(self, value: int) -> bool:
if self.isFull():
return False
else:
self.rear=(self.rear+1)%self.k
self.q[self.rear]=value
return True
def deQueue(self) -> bool:
if self.isEmpty():
return False
else:
self.q[(self.front+1)%self.k]=-1
self.front=(self.front+1)%self.k
return True
def Front(self) -> int:
return self.q[(self.front+1)%self.k]
def Rear(self) -> int:
return self.q[self.rear]
def isEmpty(self) -> bool:
return self.rear==self.front
def isFull(self) -> bool:
return (self.rear+1)%self.k==self.front
원형 큐가 가득 찬 것을 rear+1==front로 판단하기 위해 빈 공간을 하나 더 잡아서 큐를 정의했다.
책 풀이
class MyCircularQueue:
def __init__(self, k: int):
self.q = [None] * k
self.maxlen = k
self.p1 = 0
self.p2 = 0
# enQueue(): 리어 포인터 이동
def enQueue(self, value: int) -> bool:
if self.q[self.p2] is None:
self.q[self.p2] = value
self.p2 = (self.p2 + 1) % self.maxlen
return True
else:
return False
# deQueue(): 프론트 포인터 이동
def deQueue(self) -> bool:
if self.q[self.p1] is None:
return False
else:
self.q[self.p1] = None
self.p1 = (self.p1 + 1) % self.maxlen
return True
def Front(self) -> int:
return -1 if self.q[self.p1] is None else self.q[self.p1]
def Rear(self) -> int:
return -1 if self.q[self.p2 - 1] is None else self.q[self.p2 - 1]
def isEmpty(self) -> bool:
return self.p1 == self.p2 and self.q[self.p1] is None
def isFull(self) -> bool:
return self.p1 == self.p2 and self.q[self.p1] is not None
책에서는 데이터를 삽입할 때 해당 공간이 비었는지 확인하고 데이터를 삽입한 후 해당 포인터를 증가시켰다. 대신 모듈러 연산을 해서 포인터가 maxlen 보다 커지지 않게 했다.
삭제할 때는 해당 위치에 None을 넣어서 삭제를 했다. 삭제를 한 후에 front 포인터인 p1포인터를 증가시켰다.
참고한 책 : 파이썬 알고리즘 인터뷰
반응형
'Study > Algorithm' 카테고리의 다른 글
[LeetCode] #23. Merge k Sorted Lists (python) (0) | 2022.03.09 |
---|---|
[LeetCode] #641. Design Circular Deque (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 |
[LeetCode] #739. Daily Temperatures (python) (0) | 2022.02.24 |