[프로그래머스] 최대 용량이 정해진 FIFO 큐 클래스
문제
문제 설명
이번 문제에서는 다음 두 가지 일을 해야 합니다.
- 최대 용량이 정해진 FIFO 큐 클래스 구현
- 표준 입력으로 들어온 명령어로 큐 조작
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를 출력합니다. |
*pass 적은 부분을 채워넣고 명령어 기능을 구현하면 됩니다.
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):
pass
def push(self, item):
pass
def pop(self):
pass
풀이
MyQueue class에 stack1, stack2가 있는것에 주목하기!
처음엔 이걸 list나 queue라고 생각했고
테스트 케이스 1번 빼곤 다 실패가 떴다.
그래서 다시 보니 단순하게 queue를 구현하는 문제가 아니라
stack 두개를 이용해서 queue를 구현하는 문제였다.
그제서야 왜 두개나 있었는지 이해할 수 있었다.
pop 구현
먼저 pop을 구현하면 나머지도 쉽게 구현할 수 있다.
stack1에 다음과 같이 원소가 있다고 가정해보자.
queue에서 pop을 한다면 1이 나와야한다.
근데 stack1에서 pop하면 5가 나온다.
계속 pop하면 4 3 2 1.. 뽑고싶은 1이 가장 마지막에 나온다.
그럼 stack1의 원소를 반대 순서로 저장해 stack.pop을 한다면?
이 반대 순서로 저장하는 stack을 stack2라고 하자.
다음은 5를 뽑아 stack2에 저장하는 모습이다.
stack1에서 pop한 원소를 stack2에 push한다.
stack1이 빌때까지 반복한다.
다 채우면 밑 그림과 같아진다.
그럼 stack2에서 원소를 pop하면 1이 나간다.
결론은,
stack2가 비어있다면 stack1의 내용으로 다 채워주기
stack2가 비어있지 않다면? 그냥 stack2에서 빼면 된다.
qsize 구현
그럼 qsize는? stack1, stack2의 모든 원소 개수이다.
push 구현
item은 모두 stack1에만 넣으면 된다.
self.push(..)와
self.stack1.push(..), self.stack2.push(..)를 헷갈리진 말자.
위 push는 MyQueue에서의 push이고,
밑에 두 push는 MyStack에서의 push이다.
기능 구현
split()만 잊지 않으면 쉽게 구현할 수 있다.
제출 코드
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() + self.stack2.size()
def push(self, item):
if self.qsize() >= self.max_size:
return False
self.stack1.push(item)
return True
def pop(self):
try:
if self.qsize() == 0:
raise Exception("Empty Exception")
if self.stack2.size() == 0:
while self.stack1.size() != 0:
self.stack2.push(self.stack1.pop())
return self.stack2.pop()
except Exception as e:
return False
n, max_size = map(int, input().strip().split(' '))
queue = MyQueue(max_size)
while n:
command = input().strip().split(' ')
if command[0] == "PUSH":
print(queue.push(command[1]))
elif command[0] == "POP":
print(queue.pop())
elif command[0] == "SIZE":
print(queue.qsize())
n += -1
결과
정확성 테스트
| 테스트 1 〉 | 통과 (13.79ms, 7.71MB) |
| 테스트 2 〉 | 통과 (12.85ms, 7.65MB) |
| 테스트 3 〉 | 통과 (13.85ms, 7.79MB) |
| 테스트 4 〉 | 통과 (13.70ms, 7.7MB) |
| 테스트 5 〉 | 통과 (12.56ms, 7.71MB) |
| 테스트 6 〉 | 통과 (13.51ms, 7.71MB) |
채점 결과
정확성: 100.0
합계: 100.0 / 100.0