[코딩테스트 예제] 최대 용량이 정해진 FIFO 큐 클래스

이석영·2020년 12월 12일
0

Programmers

목록 보기
14/47
post-thumbnail

문제 설명
이번 문제에서는 다음 두 가지 일을 해야 합니다.

최대 용량이 정해진 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())
profile
원하는 대로 살자

0개의 댓글