ch10-1-1(leetcode 641). 원형 데크 디자인(풀이X)

* 해당 포스트는 <파이썬 알고리즘 인터뷰> 공부 후 정리 목적으로 작성되었습니다. *

* 해당 포스트는 641번 문제에 대한 정답 풀이를 포함하고 있지 않으며 공부하다 참고용으로 작성된 포스트입니다. *

 

leetcode 641번 ( https://leetcode.com/problems/design-circular-deque/ )

 

데크는 큐의 일종이지만 큐와 달리 양쪽에서 원소를 조회, 삭제, 추가할 수 있다. 

데크 역시 큐와 스택처럼 ADT이며 연결 리스트, 이중 연결 리스트, 배열 등 다양한 자료형으로 구현할 수 있다. 

 

이번 문제는 그냥 데크가 아닌 원형 데크를 연결 리스트를 사용해서 구현하는 문제이다. 이전에 원형 큐를 구현하던 것처럼, 미리 고정된 크기의 공간을 할당한 뒤 포인터를 이동하는 방식으로 구현하면 된다. 

 

다만 데크는 맨 앞과 맨 뒤에서 모두 조회, 삽입, 삭제가 가능해야 하므로, 구현이 원형 큐보다 더 복잡하다. 

 

우선 삽입이나 삭제를 하기 전에는 데크의 상태(데크가 비어 있는지, 남은 공간이 있는지)를 확인해야 하므로 해당 메소드를 먼저 구현해 보자. 

 

1. isEmpty(), isFull()

이전에 풀었던 원형 큐 구현 문제에서처럼, front 포인터와 rear 포인터 두 개가 필요하다. front 포인터는 데크의 맨 앞의 원소를, rear 포인터는 데크의 맨 뒤 원소를 가리킨다. 

원소가 아예 없는 데크를 생각해 보면 front와 rear 포인터는 같은 곳을 가리키고 있을 것이다. 원소가 삽입되면 front 또는 rear 포인터가 이동하면서 둘 사이의 거리가 벌어질 것이다. 

 

하지만 front와 rear 포인터의 값이 같다고 데크가 비어 있지 않을 수 있다. 데크가 꽉 찬 경우도 고려해야 한다. 말 그래도 '원형' 데크이기 때문에, 데크가 꽉 차면 front와 rear 포인터가 돌아서 다시 만나게 된다. 

 

이를 구분하는 방법은 front나 rear가 가리키는 인덱스에 값이 들어있는지이다. 값이 들어 있다면 full이고, 값이 없다면 empty이다. 

 

2. insertFront(), insertLast()

데크에다가 원소를 넣을 때, 맨 앞에다 넣을 수도 있고 맨 뒤에다 넣을 수도 있다. 맨 앞에 넣는 경우 front 포인터가 움직이고, 뒤에 넣으면 rear 포인터가 움직인다. 

그런데 어떻게 움직일까?

 

원형 데크는 이미 한정된 공간이 할당되어 있다. 최대 k개의 인덱스가 있고, 값이 할당되지 않은 인덱스는 null 값을 가진다. 전체 k개의 인덱스 공간 중 데크로 사용되는 공간은 front와 rear 포인터로 구분한다. front 포인터와 rear 포인터 사이에 있는 공간이 전체 k개의 인덱스 공간(사용할 수 있는 최대 공간) 중 실제 데크에서 원소가 들어가있는 부분이다. 

 

그렇다면 front와 rear의 사이가 멀어지면(원형 데크이므로, 정확히는 front에서 뒤 방향으로 이동할 때 rear이 더 멀어지면) 데크에는 원소가 추가되는 것이고, 반대로 front와 rear가 가까워지면 데크에서 원소가 삭제된다고 볼 수 있다. 

 

즉 front이 앞으로 한 칸 이동하면 front와 rear의 거리가 멀어지므로 데크에 원소가 추가되었다고 볼 수 있다. (insertFront)

또한 rear이 뒤로 한 칸 이동해도 front와 rear의 거리가 멀어지므로 데크에 원소가 추가된 것이다. (insertLast)

 

3. deleteFront(), deleteLast()

위의 경우와 반대로 front이 뒤로 한 칸 이동한다면 front와 rear의 거리가 가까워진다. 그러므로 데크에서 원소가 삭제되었다고 볼 수 있다. 현재 front가 가리키던 원소에다가 null 값을 할당해준 뒤 front 포인터를 뒤로 한 칸 옮겨서 구현할 수 있다. 

 

rear을 앞으로 한 칸 이동시켜도 같은 결과가 나온다. 

다만 front은 맨 앞 원소를 가리키지만 rear은 맨 뒤의 원소의 다음 인덱스(데크가 full이나 empty 상태라면 front와 같은 인덱스, 아니라면 빈 공간을 가리킨다)를 가리키므로, rear을 앞으로 한 칸 이동시킨 뒤 해당 인덱스에 null 값을 할당하면 된다. 

 

4. getFront(), getLast()

데크에 추가나 삭제를 하지 않으므로 포인터가 이동하지는 않는다. 다만 두 메소드 모두 사용 전 데크가 비었는지를 확인해야 하겠다. 

getFront()의 경우 front 포인터가 가리키는 원소를, getLast()의 경우 rear 포인터보다 한 칸 앞 위치에 있는 원소를 리턴하면 된다. 

 

 

전체 코드는 다음과 같다. 

(교재를 참고하지 않고 코드를 작성하였습니다.)

class MyCircularDeque(object):

    def __init__(self, k):
        self.deque = [None] * k
        self.size = k
        self.front = 0
        self.rear = 0

    def insertFront(self, value):
        if self.isFull():
            return False
        self.front = (self.front - 1) % self.size
        self.deque[self.front] = value
        return True

        
    def insertLast(self, value):
        if self.isFull():
            return False
        self.deque[self.rear] = value
        self.rear = (self.rear + 1) % self.size
        return True
        
    def deleteFront(self):
        if self.isEmpty():
            return False
        self.deque[self.front] = None
        self.front = (self.front + 1) % self.size
        return True
        
    def deleteLast(self):
        if self.isEmpty():
            return False
        self.rear = (self.rear - 1) % self.size
        self.deque[self.rear] = None
        return True
        
    def getFront(self):
        if self.isEmpty():
            return -1
        return self.deque[self.front]
        
    def getRear(self):
        if self.isEmpty():
            return -1
        position = (self.rear - 1) % self.size
        return self.deque[position]
        
    def isEmpty(self):
        if self.front == self.rear and self.deque[self.front] is None:
            return True
        return False
        
    def isFull(self):
        if self.front ==  self.rear and self.deque[self.front] is not None:
            return True
        return False