알고리즘 선택 트랙 [5일차]

<문제>

큐2 백준 18258 문제

 

<문제 회고>

이 문제를 보았을때는 저번에 스택 문제가 떠올랐다.

그래서 나는 리스트를 사용하였다.

근데 처음에 시간 초과가 나왔다.

해당 코드는 다음과 같다.

# 시간 초과 코드
import sys
n = int(input())

q = []

for i in range(n):

data = list(map(str,sys.stdin.readline().split()))

if data[0] == "pop":
	if len(q) != 0:
		print(q.pop(0))
	else:
		print(-1)
if data[0] == "size":
	print(len(q))
if data[0] == "empty":
	if len(q) == 0:
		print(1)
	else:
		print(0)
if data[0] == "front":
	if len(q) != 0:
		print(q[0])
	else:
		print(-1)
if data[0] == "back":
	if len(q) != 0:
		print(q[-1])
	else:
		print(-1)
if data[0] == "push":
q.append(data[1])

이유를 찾아보니 리스트에서 push 메소드는 0(1)의 시간복잡도가 걸리지만 pop 메소드는 0(n)의 시간복잡도가 걸린다.

그럼 여기서 pop 메소드는 왜 0(n)의 시간 복잡도를 가질까?

그 이유를 내 나름대로 정리를 해보았다.

먼저 포인터는 배열의 마지막부터 시작한다. 그리고 큐에서의 pop은 첫번째 원소를 뽑아오는 것이기 때문에 포인터는 첫번째 원소까지 쭉 찾아야 한다. 

그래서 0(n)의 시간복잡도를 가지는 것이다.

 

그래서 나는 deque라는 자료구조를 이용했다. deque는 링 버퍼로 이루어져있다. 여기서 링 버퍼란 배열에 맨 끝의 원소 뒤에 맨 앞의 원소가 연결되는 자료구조를 뜻한다. 따라서 deque의 pop 메소드 시간복잡도는 0(1)이다. 왜냐하면 맨 마지막 원소와 맨 앞의 원소가 연결되어있기 때문이다. 따라서 맨 앞의 원소를 찾는데 모든 원소를 돌 필요가 없다.

그래서 나는 deque라는 자료구조를 통해서 위의 문제를 해결했다.

 

해결 코드

import sys
from collections import deque
n = int(input())

q = deque()


for i in range(n):
data = list(map(str,sys.stdin.readline().split()))
#push
if data[0] == "push":
    q.append(data[1])
elif data[0] == "pop":
    if len(q)!= 0:
        print(q.popleft())
    else:
        print(-1)
elif data[0] == "size":
    print(len(q))
elif data[0] == "empty":
    print(int(bool(not q)))
elif data[0] == "front":
    if len(q) != 0:
        print(q[0])
    else:   
        print(-1)
elif data[0] == "back":
    if len(q) != 0:
        print(q[-1])
    else:
        print(-1)

 

좀더 조사해 보니 이런 내용이 있네요 !!

스택의 리스트는 pop()은 시간복잡도 = 0(n)

디큐의 리스트는 pop()은 시간복잡도 = 0(1)

이다.