백준18258 문제 보러가기

문제

정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여섯 가지이다.

push X: 정수 X를 큐에 넣는 연산이다.
pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
size: 큐에 들어있는 정수의 개수를 출력한다.
empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
입력
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

예제 입력 1

15
push 1
push 2
front
back
size
empty
pop
pop
pop
size
empty
pop
push 3
empty
front

예제 출력 1

1
2
2
0
1
2
-1
0
1
-1
0
3

문제 해결 과정

자료구조에 대한 지식

해당 문제는 큐를 구현하는 문제였다.
나는 문제만 읽고 쉽게 해결할 수 있을 것이라고 생각했다.
파이썬 라이브러리를 이용한 queue에 담아서, 명령에 맞게 구현하면 될 거라고 생각해서 처음에는 이렇게 짰다.

import queue

que = []

N = int(input())

for _ in range(N) :
    exe = list(map(str, input().split()))
    if exe[0] == 'push' :
        number = int(exe[1])
        que.append(number)
    elif exe[0] == 'front' :
        if len(que) == 0 : print(-1)
        else:
            number = que[0]
            print(number)
    elif exe[0] == 'back' :
        if len(que) == 0 : print(-1)
        else:
            l = len(que)
            number = que[l-1]
            print(number)
    elif exe[0] == 'pop' :
        if len(que) == 0 : print(-1)
        else :
            number = que.pop()
            print(number)
    elif exe[0] == 'empty' :
        l = len(que)
        if l == 0 : print(1)
        else : print(0)
    else :
        l = len(que)
        print(l)

나름 잘 짰다고 생각하고, 제출을 했는데 런타임 에러가 떴다.
왜지..? 문제가 없는데 여기서 다른 예외 상황이 생길 수 있나?
라는 생각을 했다.
그래서 혹시나 라이브러리 사용 때문에 틀렸나 싶어서 라이브러리를 빼고 List를 써서 구현을 했지만, 이번엔 시간초과가 떴다.

Stack / Queue / Deque의 차이점

Stack(스택)은 한쪽에서만 자료를 넣고 뺄 수 있는 후입선출 LIFO(Last In First Out)형식의 선형 자료구조이다. 예를 들면, 상자를 3개를 순서대로 쌓았다고 가정해보자. 첫 번째로 쌓은 상자는 두 번째, 세 번째 상자의 제거없이 꺼낼 수가 없다.

Queue(큐)도 Stack과 마찬가지로 한쪽에서 자료를 넣지만, 차이점은 자료를 넣은 곳 반대 쪽에서 제거가 일어난다. 선입선출 FIFO(First In First Out) 형식의 선형 자료구조이다. 삭제 연산이 수행하는 곳은 프론트(front), 삽입 연산만 이루어지는 곳은 리어(rear)라고 한다. 그리고 리어에서 삽입 연산을 인큐(enQueue), 프론트에서 삭제 연산을 디큐(dnQueue)라고 한다. deque는 스택과 큐의 장점을 모두 채택한 것인데 데이터를 넣고 빼는 속도가 리스트 자료형에 비해 효율적이며 queue 라이브러리를 이용하는 것보다 더 간단하다.

Dequeue(덱)이란, 양쪽에서 삽입과 삭제가 가능한 구조이며 스택과 큐의 연산을 모두 지원한다.

자세한 시간 복잡도 차이를 보면 다음과 같다.

거의 모든 부분에서 Deque이 시간 부문에서 유리한 것을 확실할 수 있다.
그래서 나는 Deque에 숫자들을 넣어서 구현했다.

전체 코드는 다음과 같다.

import sys

from collections import deque

que = deque()

N = int(input())

for _ in range(N) :
    exe = sys.stdin.readline().split()
    if exe[0] == 'push' :
        number = int(exe[1])
        que.append(number)
    elif exe[0] == 'front' :
        if len(que) == 0 : print(-1)
        else:
            number = que[0]
            print(number)
    elif exe[0] == 'back' :
        if len(que) == 0 : print(-1)
        else:
            number = que[-1]
            print(number)
    elif exe[0] == 'pop' :
        if len(que) == 0 : print(-1)
        else :
            number = que.popleft()
            print(number)
    elif exe[0] == 'empty' :
        l = len(que)
        if l==0 :
            print(1)
        else : print(0)
    else :
        l = len(que)
        print(l)