[LeetCode] 622. Design Circular Queue 원형 큐 디자인

파이썬으로 배우는 알고리즘 책을 공부하며 풀었던 LeetCode문제들을 재정리해보자.

 

# 문제 설명 

622번 Design Circular Queue는 원형 큐를 디자인 하는 문제이다.

 

구현해야 하는 함수

 

| 원형 큐 원리 | 

앞쪽의 공간이 남아있을때, 끝과 앞쪽을 연결하여 앞쪽으로도 추가할 수 있도록 재활용 가능한 구조이다. 

크기가 4인 원형 큐 

크기가 3인 원형 큐 

 

# 풀이방법 1  (내 풀이)

class MyCircularQueue:

    def __init__(self, k: int):
        # print("init")
        self.q = [None] * k
        self.q_len = k
        self.front_p = 0
        self.rear_p = 0
        
    def enQueue(self, value: int) -> bool:
        # print("enQueue : ", self.front_p, self.rear_p, self.q)
        if self.q[self.rear_p] is None : 
            self.q[self.rear_p] = value 
            self.rear_p = (self.rear_p + 1) % self.q_len
            return True
        else : 
            return False

    def deQueue(self) -> bool:
        # print("deQueue : ", self.front_p, self.rear_p, self.q)
        if self.q[self.front_p] is not None : 
            self.q[self.front_p] = None
            self.front_p = (self.front_p + 1) % self.q_len
            return True
        else : 
            return False

    def Front(self) -> int:
        # print("Front : ", self.front_p, self.rear_p, self.q)
        if self.q[self.front_p] is None:
            return -1
        else : 
            return self.q[self.front_p]

    def Rear(self) -> int:
        # print("Rear : ", self.front_p, self.rear_p, self.q)
        if self.q[self.rear_p-1] is None :
            return -1
        else : 
            return self.q[self.rear_p-1]

    def isEmpty(self) -> bool:
        # print("isEmpty : ", self.front_p, self.rear_p, self.q)
        if self.front_p == self.rear_p and self.q[self.front_p] is None :
            return True
        else : 
            return False

    def isFull(self) -> bool:
        # print("isFull : ", self.front_p, self.rear_p, self.q)
        if self.front_p == self.rear_p and self.q[self.front_p] is not None  :
            return True
        else :
            return False


# Your MyCircularQueue object will be instantiated and called as such:
# obj = MyCircularQueue(k)
# param_1 = obj.enQueue(value)
# param_2 = obj.deQueue()
# param_3 = obj.Front()
# param_4 = obj.Rear()
# param_5 = obj.isEmpty()
# param_6 = obj.isFull()

| 아이디어  | 

배열과, front_p. reer_p 투 포인터를 두어서, 마지막 위치와 시작 위치를 연결하는 원형 구조를 만든다. 

값 추가 시(enQueue)에는 rear_p포인터를 이용하여 값을 추가하고, 값을 삭제 시(deQueue)엔 front_p를 움직여 값을 삭제한다.

 

empty인경우와 full 인경우 front_p와 rear_p 포인터가 같은 인덱스를 가르키는데, 이때 다른 점은 가리키는 인덱스에 값의 여부이다. 이 점을 이용하여 코드를 작성하였다.  

 

 

| 코드 수정 (책 잠고) | 

if self.front_p == self.rear_p and self.q[self.front_p] is None :

            return True

        else :

            return False

 

위에서 작성한 나의 코드를 보면 if문의 조건문을 이용하여 return 값을 다르게 설정하였는데, 책의 코드를 보면 if문을 사용하지 않고 다음과 같이 한 줄로 return 값을 설정하였다. 코드 길이가 훨씬 줄어들었으니 앞으로 이 방법을 이용하여 코드 작성해야겠다. 

 

return self.front_p == self.rear_p and self.q[self.front_p] is None

 

 

| 핵심 |

empty인경우와 full 인경우 front_p와 rear_p 포인터가 같은 인덱스를 가르키는데, 이때 다른 점은 가리키는 인덱스에 값의 여부이다.

 

 

# 결과 

초반에 포인터 작성시 self. 을 이용하지 않고, 바로 front_p 이런식으로 작성하였다. 

또한 empty와 full 일 때 포인터 위치를 잘 파악하지 못하여 submit에서 많이 틀렸다.