문제 설명
이번 문제에서는 다음 두 가지 일을 해야 합니다.
최대 용량이 정해진 FIFO 큐 클래스 구현1
표준 입력으로 들어온 명령어로 큐 조작
1. 최대 용량이 정해진 FIFO 큐 클래스 구현
스택 두 개를 통해 최대 용량이 max_size가 정해진 FIFO 큐 클래스, MyQueue를 구현하세요. 구현할 메소드는 다음과 같습니다.
qsize()
큐가 가진 원소 수를 리턴합니다.
push(x)
입력받은 인자, x를 큐에 넣습니다.
단, 현재 큐가 꽉 찬 경우 인자를 넣지 말고 False를 리턴하세요.
pop():
큐가 가진 원소 중, 가장 처음에 들어온 원소를 큐에서 제거하고 리턴합니다.
큐에 원소가 없다면 Empty Exception을 raise 하세요. Empty Exception은 본인이 직접 만드셔야 합니다.
※ 주의사항
위 메소드를 구현할때에는 주어진 MyStack 클래스를 변경하지 말아주세요.
MyQueue 클래스에서 MyStack 클래스의 변수인 lst를 직접 접근하지 않아야합니다. ex) self.stack1.lst 처럼 접근 금지
2. 표준 입력으로 들어온 명령어로 큐 조작
첫 줄에는 앞으로 들어올 명령어 수 n과 큐의 최대 크기인 max_size가 공백으로 구분되어 주어집니다.
그 뒤로는 N 줄에 걸쳐, 큐를 조작할 명령어가 주어집니다.
명령어 종류 result
SIZE 현재 큐에 들은 원소 수를 출력합니다.
PUSH X 정수 X를 큐에 넣습니다. 성공했다면 True를, 아니라면 False를 출력합니다.
POP 큐에서 원소를 빼냅니다. 성공했다면 빼낸 원소를, 아니라면 False를 출력합니다.
제한 조건
n은 1 이상 100 이하입니다.
max_size는 1 이상 100 이하입니다.
PUSH 명령어에서 들어오는 X는 -100 이상 100 이하인 정수입니다.
입출력 예
입력
5 1
PUSH 3
PUSH -5
POP
SIZE
POP
출력
True
False
3
0
False
설명
명령어는 5개, 큐의 최대 허용량은 1입니다.
명령어 결과
PUSH 3 큐에 3이 들어갑니다. True를 출력합니다.
PUSH -5 큐가 꽉 찼습니다. 더 이상 원소를 넣을 수 없어 False를 출력합니다.
POP 큐의 원소 중, 가장 먼저 들어간 3을 꺼냅니다. 따라서 3을 출력합니다.
SIZE 큐에 남은 원소는 0개 이므로, 0을 출력합니다.
POP 큐에 원소가 없으므로 False를 출력합니다.
이 문제의 핵심은 스택을 2개 이용해서 큐를 만드는 것이다. 큐는 FIFO특징을 가지고있기 때문에 LIFO 특징을가진 2개의 스택이있을 때 한쪽에서 다른 한쪽으로 옮긴 후 꺼낸다고 생각하면 쉽게 구현가능하다. 다만 이 문제는 코드로 2가지를 구현해야하는데 2번제 문제인 표준 입력으로 들어온 명령어로 큐 조작에 대해 문제이해를 제대로하지 못해 해결하는데 시간이 꽤 걸렸다.
내가 작성한 코드
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
## 각 스택1과 스택2에있는 원소의 개수합을 반환하였다.
def qsize(self):
return self.stack1.size() + self.stack2.size()
## 스택이 가득차있다면 False를 반환할 것이고 그렇지않으면 스택1에 item을 넣은후 다시 스택1이 비워질 때까지 꺼내서 스택2에 넣으면 스택2에 있는 원소들은 스택1과 반대로 쌓이기 때문에 큐와 같다고 볼 수 있다.
def push(self, item):
if self.stack1.size() == self.max_size:
return False
else:
self.stack1.push(item)
return True
## 스택이 비어있으면 False를 반환하고 그렇지않은 경우 스택1의 원소를 모두 스택2로 옮긴후 스택2에서 pop()함수를 사용해야 가장 먼저 입력된 것이 제거된다.
def pop(self):
try:
if self.stack2.size() == 0:
while self.stack1.size() != 0:
self.stack2.push(self.stack1.pop())
return self.stack2.pop()
except:
# print('Empty Exception')
return False
n, max_size = map(int, input().strip().split(' '))
# print(n, max_size)
## 최대사이즈 max_size인 큐를 생성한다.
q = MyQueue(max_size)
for _ in range(n):
m = input()
L = m.split(' ')
if L[0] == 'SIZE':
print(q.qsize())
elif L[0] == 'PUSH':
print(q.push(int(L[1])))
elif L[0] == 'POP':
print(q.pop())