프로그래머스 - 최대 용량이 정해진 FIFO 큐 클래스

1. 문제

 

2. 소스코드(Python3)

class MyStack(object):
    def __init__(self):
        self.lst = list()

    def push(self, x):
        self.lst.append(x)

    def pop(self):
        return self.lst.pop()

    def size(self):
        return len(self.lst)

class MyQueue(object):
    def __init__(self, max_size):
        self.stack1 = MyStack()
        self.stack2 = MyStack()
        self.max_size = max_size

    def qsize(self):
        return self.stack1.size()

    def push(self, item):
        if self.qsize() == self.max_size:
            return False
        else:
            while self.stack1.size():
                self.stack2.push(self.stack1.pop())
            self.stack1.push(item)
            while self.stack2.size():
                self.stack1.push(self.stack2.pop())
            return True
                

    def pop(self):
        if self.qsize() == 0:
            return False
        else:
            return self.stack1.pop()
    
n, max_size = map(int, input().strip().split(' '))
fifoq = MyQueue(max_size)
for i in range(n):
    inst = input()
    if 'PUSH' in inst:
        inst, X = inst.split(' ')
        print(fifoq.push(X))
    elif 'POP' in inst:
        print(fifoq.pop())
    else:   #size
        print(fifoq.qsize())

 

3. 고찰

1) 문제 이해

처음 문제를 풀었을 때, 왜 MyQueue클래스에서 두 개의 스택을 생성했는지 이해가 안 갔었다.

스택을 이용해서 큐를 만드는 문제인데, 스택으로 스택을 만들어서 채점에 실패했었다.

질문을 올렸는데, 프로그래머스 팀원분이 알려주셔서 문제를 제대로 풀었다.

 

2) 알고리즘

큐는 FIFO이기 때문에, 어떠한 원소를 넣으면 스택의 top에 저장하도록 구현하였다.

stack1은 원소들을 저장하는 공간이고, stack2는 원소들을 잠시 옮겨놓는 임시 공간으로 사용하였다.

qsize함수는 stack1의 사이즈를 리턴하였다.

push함수는 만약 큐가 꽉 차있으면 False를 리턴하였고,

아니라면 stack1이 빌 때까지 stack1의 원소를 pop하여 stack2에 push,

stack1에 해당 item을 넣은 후에

다시 stack2가 빌 때까지 stack2의 원소를 pop하여 stack1에 push하였다.

예를 들어, stack1에 [1, 2, 3]순서로 원소들이 있었으면, stack2에는 [3, 2, 1]순으로 임시 저장된다.

stack1에 새 item(4)을 넣고

다시 stack2의 원소들을 stack1으로 옮기면, stack1은 [4, 1, 2, 3]이 된다.

pop함수는 큐에서 새 원소를 삽입할 때 큐의 top에 저장했기 때문에 바로 pop하였다.