[백준 18258번 문제] 큐 2

이 문제는 큐를 구현하는 문제이다. 각 명령어를 입력할 때마다 주어진 조건에 맞게 결과를 출력하면 된다.

처음에 for문안에 조건문을 이용해서 문제를 풀었는데 push 1 이렇게 문자열과 숫자가 같이 있는 경우를 어떻게 해야할지 고민이였다.

if "push" in msg:
        m, num = map(str, msg.split(' '))
        num = int(num)

이런식으로 msg = input()으로 입력받아서 split메소드를 이용해서 숫자를 따로 저장할 생각이였다

그리고 "push" in msg 이런식으로 입력받은 값안에 명령어를 확인해서 조건문으로 처리했는데 시간초과가 발생하였다ㅠ

 

그래서 다른 방법을 검색해 보니깐 deque를 사용하는 방법이 있어서 해결했다.

나머지 명령어 조건문은 동일한데 pop을 한경우에 pop 메소드를 사용하면 첫번째 숫자를 pop 제거하고 한 칸씩 당기는 과정해서 O(n)의 계산량이 발생해서 시간초과가 발생한 것이였다.

elif "pop" in msg:
        if len(queue) == 0:
            print(-1)
        else:
            print(queue[0])
            queue.pop(0)

그래서 deque함수를 이용해서 popleft라는 간단한 메소드를 이용했더니 시간초과 문제가 해결되었다.

elif msg[0] == 'pop':
        if len(queue) == 0:
            print(-1)
        else:
            print(queue.popleft())

deque를 이용하지 않고 푸는 또 다른 방법으로는 리스트에서 삭제하고 한칸씩 앞으로 당기지 말고 가르키는 위치를 계속 변경해주면 좋을거 같다.

 

<전체코드>

import sys
from collections import deque
input  = sys.stdin.readline

num = int(input())
queue = deque([])

for i in range(num):
    msg = input().split()
    if msg[0] == 'push':
        queue.append(msg[1])
    elif msg[0] == 'pop':
        if len(queue) == 0:
            print(-1)
        else:
            print(queue.popleft())
    elif msg[0] == 'size':
        print(len(queue))
    elif msg[0] == 'empty':
        if len(queue) == 0:
            print(1)
        else:
            print(0)
    elif msg[0] == 'front':
        if len(queue) == 0:
            print(-1)
        else:
            print(queue[0])
    elif msg[0] == 'back':
        if len(queue) == 0:
            print(-1)
        else:
            print(queue[-1])