큐(Queue) - 백준 18258 파이썬

 

큐(Queue)란 기본적인 자료구조의 한 가지로,

먼저 들어온 데이터가 먼저 나가는( FIFO - First In First Out - ) 구조로 데이터를 저장하는 방식을 말합니다.

 

실생활에 적용해보자면, 먼저 주문한 손님에게 먼저 음식이 나가는 것이라고 생각할 수 있습니다.

 

아래의 그림과 같이 각 테이블에서 주문을 하면 주문표가 순서대로 들어옵니다. 주방에서는 주문이 들어온 순서대로 요리해 손님에게 보냅니다.

 

백준에 나와있는 큐 문제를 풀어보겠습니다.

입력 : 

15

push 1

push 2

front

back

size

empty

pop

pop

pop

size

empty

pop

push 3

empty

front

 

큐의 가장 중요한 기능은 push와 pop입니다.

push일 경우 데이터를 추가. pop일 경우 맨 앞의 데이터 뽑고 제거입니다.

from sys import stdin

repeat = int(input())

queue = []

# 출력되는 숫자들을 확인하기위해 따로 뺐습니다.
# 하나하나 출력하고 싶다면 output_list.append부분을 print로 바꿔주시면 됩니다.
output_list = []
cnt = 0

for i in range(repeat):
    cmd = stdin.readline()

    # 입력받은 명령어의 첫단어를 확인합니다.
    if cmd[0] == 's':
        output_list.append(len(queue))

    elif cmd[0] == 'e':
        if len(queue) == 0:
            output_list.append(1)
        else:
            output_list.append(0)

    elif cmd[0] == 'f':
        if len(queue) == 0:
            output_list.append(-1)
        else:
            output_list.append(queue[0])

    elif cmd[0] =='b':
        if len(queue) == 0:
            output_list.append(-1)
        else:
            output_list.append(queue[-1])

    # push와 pop에대한 동작.
    elif cmd[0] == 'p' :
        # pop일 경우 맨 앞의 데이터를 추출하고 제거합니다.
        if cmd[1] == 'o':
            if len(queue) != 0:
                output_list.append(queue[0])
                del queue[0]
            else:
                output_list.append( -1 )
        # push일 경우 데이터를 추가합니다.( 리스트와 동일 )
        else:
            num = int(cmd.split()[1])
            queue.append( num )


print(output_list)

하지만 이렇게 제출시 백준에서는 시간초과가 나옵니다. 

 

알아보니 리스트에서는 데이터 삭제시 리스트의 모든 데이터를 앞으로 하나씩 이동하기 때문에 O(n)만큼의 시간복잡도가 추가된다고 합니다.

-> 이 시간을 줄이기 위해 queue의 동작을 최적화한 라이브러리를 사용합니다.( from collections import deque )

from sys import stdin
from collections import deque

repeat = int(input())
queue = deque()

for i in range(repeat):
    cmd = stdin.readline()

    if cmd[0] == 's':
        print(len(queue))

    elif cmd[0] == 'e':
        if len(queue) == 0:
            print(1)
        else:
            print(0)

    elif cmd[0] == 'f':
        if len(queue) == 0:
            print(-1)
        else:
            print(queue[0])

    elif cmd[0] =='b':
        if len(queue) == 0:
            print(-1)
        else:
            print(queue[-1])
    
    elif cmd[0] == 'p' :
        if cmd[1] == 'o':
            if len(queue) != 0:
                print(queue.popleft())
            else:
                print( -1 )

        else:
            num = int(cmd.split()[1])
            queue.append( num )

deque() 함수를 사용해 만든 queue에서는

pop시 queue.popleft() 합니다.

-> 맨 앞의 데이터를 출력하고 제거합니다. 리스트와 같이 데이터를 옮기는 과정이 없어 시간초과 문제가 발생하지 않습니다.

push시에는 리스트와 똑같이 queue.append()로 데이터를 추가합니다.

 

18258번: 큐 2