[BACKJOON] len() & 원형 queue

요즘 자료구조 문제를 풀기 시작했는데, queue와 deque을 사용해야만 문제가 시간내에 처리가 가능한 것을 보다보니 무조건 전에 사용하던 방식으로만 풀려고 하는 경향을 발견했다.

하지만 이번에 푼 1158 문제는 도리어 쉽게 생각했어야 했던 문제이다. 주어진 칸을 건너 뛰어서 만나는 숫자를 누적해서 출력하는 문제로, 그 건넌다는 것을 처리하기 위해 2개의 queue를 사용했지만 시간 초과가 떴었다.

하지만 돌아가는 방식의 list를 활용하는 문제는 원형큐도 아니고, 단지 index가 돌아갈 수 있게 처리하면 되는 문제였다.

시간복잡도 - len()

len()은 len()을 호출하고, 카운터로 작동하며 데이터가 정의되고 저장되면 자동적으로 증가한다. 그래서 인터프리터에게 순회하며 길이를 가져오라는 명령 대신 이미 저장된 value를 가져오게 된다.

이렇게 len()이 O(1)을 가져서 직접 값을 옮기는 경우마다 추가 조건을 확인하는 것에 비해 덜 시간을 걸려서 시간초과가 발생하지 않게 된다.

---

위 문제를 고민하면서 찾아본 큐에 대해 간략히 정리해보았다.

원형 queue

front와 rear가 존재한다. rear는 마지막 요소 위치를 가리키고, front는 시작되는 요소가 아닌 그 시작 요소의 앞에 빈 위치를 가리킨다. 그래서 원형 큐가 다 찼다는 것은 (rear+1)%MAX == front를 통해 확인한다.
삭제는 front 인덱스에 +1을 통해 표현하고, 삽입은 rear+1에 새로운 값을 넣고 rear를 +1로 만드는 자료구조이다.

하지만 python에서는 삭제시, 인덱스가 자동으로 당겨지기 때문에 실제로 list에서 삭제하는 것이 아닌 시작 인덱스가 뒤로 가게 하는 것으로 만든다.

MAX = 10
class CircularQueue :
    def __init__(self):
        self.front = 0
        self.rear = 0
        self.items = [None] * MAX
        
    def isEmpty(self):
        return self.front == self.rear
    
    def isFull(self):
        return self.front == (self.rear+1)%MAX
    
    def enqueue(self, item):
        if not self.isFull():
            self.rear = (self.rear + 1) % MAX
            self.items[self.rear] = item
            
    def dequeue(self):
        if not self.isEmpty():
            self.front = (self.front+1) % MAX
            return self.items[self.front]
            
    def peek(self):
        if not self.isEmpty():
            return self.items[(self.front+1)%MAX]
            

---