[LeetCode] 641. design_circular_deque (Medium) 2023/5/11

알고리즘🥚/문제풀이 (Python)

[LeetCode] 641. design_circular_deque (Medium) 2023/5/11

🪄하루🪄 2023. 5. 11. 08:11

728x90

문제 제목	정답률	난이도
641. design_circular_deque	57.2%	Medium

Design Circular Deque - LeetCode

Can you solve this real interview question? Design Circular Deque - Design your implementation of the circular double-ended queue (deque). Implement the MyCircularDeque class: * MyCircularDeque(int k) Initializes the deque with a maximum size of k. * boole

leetcode.com

문제요약

다음 연산을 제공하는 원형 데크를 만들어라

def __init__(self, k: int): k 크기의 원형데를 선언
def insertFront(self, value: int) -> bool: value 값을 head 왼쪽에 삽입하는 함수
def insertLast(self, value: int) -> bool: value 값을 tail 오른에 삽입하는 함수
def deleteFront(self) -> bool: 원형데크의 head 인덱스의 값을 삭제하는 함수
def deleteLast(self) -> bool: 원형데크의 tail 인덱스의 값을 삭제하는 함수
def Front(self) -> int: 원형데크의 head 인덱스의 값을 반환하는 함수
def Rear(self) -> int: 원형데크의 tail 인덱스의 값을 반환하는 함수
def isEmpty(self) -> bool: 원형데크가 비었는지 판단하는 함수
def isFull(self) -> bool: 원형데크에 여분의 자리가 없는지 판단하는 함수

풀이 1

원형 디큐는 리스트와, head, tail 인덱스를 이용하여 구현할 수 있다.

구현 순서는 구현하기 용이한 것부터 한다

모든 함수를 구현할 때,

일반적인 경우
head, tail 인덱스가 리스트의 제일 첫자리(0)와 제일 끝자리(len(원형큐)-1)에 있는 경우를 나누어 생각하자(해당 인덱스의 다음 인덱스는 제일 끝자리와 제일 첫자리이기 때문이다)

__init__

front, rear

isEmpty, isFull

insertFront, insertLast, deleteFront, deleteLast

구현 (96ms)

class MyCircularDeque:
    def __init__(self, k: int):
        self.head, self.tail=0, 0
        self.q=[None]*k

    def insertFront(self, value: int) -> bool:
        if self.isFull():
            return False
        if self.isEmpty()==False:
            if self.head==0:
                self.head=len(self.q)-1
            else:
                self.head-=1
        self.q[self.head]=value
        return True

    def insertLast(self, value: int) -> bool:
        if self.isFull():
            return False
        if self.isEmpty()==False:
            if self.tail==len(self.q)-1:
                self.tail=0
            else:
                self.tail+=1
        self.q[self.tail]=value
        return True

    def deleteFront(self) -> bool:
        if self.isEmpty():
            return False
        self.q[self.head]=None
        if self.head!=self.tail:
            if self.head==len(self.q)-1:
                self.head=0
            else:  
                self.head+=1
        return True

    def deleteLast(self) -> bool:
        if self.isEmpty():
            return False
        self.q[self.tail]=None
        if self.head!=self.tail:
            if self.tail==0:
                self.tail=len(self.q)-1
            else:
                self.tail-=1
        return True

    def getFront(self) -> int:
        if self.isEmpty():
            return -1
        return self.q[self.head]

    def getRear(self) -> int:
        if self.isEmpty():
            return -1
        return self.q[self.tail]

    def isEmpty(self) -> bool:
        return self.q[self.head]==None
        
    def isFull(self) -> bool: 
        if self.tail==len(self.q)-1:
            return self.head==0 and self.tail!=None
        else: #tail<head 인 경우
            return self.tail==(self.head-1)

728x90

저작자표시 비영리 변경금지

'알고리즘🥚 > 문제풀이 (Python)' 카테고리의 다른 글

[Programmers] 기둥과 보 설치 (Lv.3) 2024/4/1 (1)	2024.04.01
[Programmers] 자물쇠와 열쇠 (Lv.3) 2024/3/31 (0)	2024.03.31
[LeetCode] 622. design_circular_queue (Medium) 2023/5/10 (0)	2023.05.10
[LeetCode] 232. implement_queue_using_stacks (Easy) 2023/5/10 (0)	2023.05.10
[LeetCode] 739. daily_temperatures (Medium) 2023/5/9 (0)	2023.05.09

현재글[LeetCode] 641. design_circular_deque (Medium) 2023/5/11

Today :
Yesterday :

일	월	화	수	목	금	토
						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

🐇꾸준히, 한걸음씩☘️