문제
정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
명령은 총 여섯 가지이다.
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문제 풀이
시간초과한 풀이
import sys
input=sys.stdin.readline
N=int(input())
queue=[]
def empty(q):
if len(q)==0:
return 1
else:
return 0
for _ in range(N):
temp=input().split()
if temp[0]=='push':
queue.append(temp[1])
elif temp[0]=='pop':
if empty(queue)==1:
print(-1)
else:
print(queue.pop(0))
elif temp[0]=='size':
print(len(queue))
elif temp[0]=='empty':
print(empty(queue))
elif temp[0]=='front':
if empty(queue)==1:
print(-1)
else:
print(queue[0])
elif temp[0]=='back':
if empty(queue)==1:
print(-1)
else:
print(queue[-1])위 코드로 짰더니 시간초과가 발생했다. 알고리즘을 풀다가 queue.pop(0)을 이용하는것보다 deque의 popleft()를 사용하는 것이 시간효율이 좋다고 했던 것이 생각나 deque로 고쳤다.
성공한 풀이
from collections import deque
import sys
input=sys.stdin.readline
N=int(input())
queue=deque([])
def empty(q):
if len(q)==0:
return 1
else:
return 0
for _ in range(N):
temp=input().split()
if temp[0]=='push':
queue.append(temp[1])
elif temp[0]=='pop':
if empty(queue)==1:
print(-1)
else:
print(queue.popleft())
elif temp[0]=='size':
print(len(queue))
elif temp[0]=='empty':
print(empty(queue))
elif temp[0]=='front':
if empty(queue)==1:
print(-1)
else:
print(queue[0])
elif temp[0]=='back':
if empty(queue)==1:
print(-1)
else:
print(queue[-1])우선 queue를 deque를 이용하여 선언해준다.
그리고 문제의 요구사항대로 구현해준다.
- push :
append로 값을 추가해준다. - pop :
deque.popleft()를 이용하여 왼쪽 값을 pop 해준다. queue에 값이 없을때에는 미리 만들어둔empty함수를 이용하여-1을 출력한다. - size : queue의 사이즈를 구해준다.
- empty : queue의 길이를 구해 0인 경우에는
1을 출력하고 아닌 경우에는0을 출력한다. - front : queue의 제일 첫 값을 출력한다. queue에 값이 없을때에는 미리 만들어둔
empty함수를 이용하여-1을 출력한다. - back : queue의 제일 마지막 값을 출력한다. queue에 값이 없을때에는 미리 만들어둔
empty함수를 이용하여-1을 출력한다.
deque
배열을 사용하여 pop(0)을 사용하면 배열의 길이에 따라 시간복잡도가 달라진다. 즉, 배열 길이만큼 O(n) 시간이 걸린다.
하지만 deque는 양방향 자료형이기 때문에 popleft()를 사용하면 O(1)의 시간이 걸린다.
아래는 실제로 pop(0)과 popleft()를 사용했을 때의 시간을 측정한 결과이다.
import time
from collections import deque
queue_1=[i for i in range(1000000)]
queue_2=deque([i for i in range(1000000)])
cur_time=time.time()
print(queue_1.pop(0))
print(time.time()-cur_time)
cur_time=time.time()
print(queue_2.popleft())
print(time.time()-cur_time)결과
0
0.010133028030395508
0
0.00012302398681640625결과를 보면 알 수 있듯이 deque.popleft()를 사용하면 시간이 훨씬 적게 걸린다. queue를 이용할때는 deque를 이용하는게 좋을 것 같다는 생각이 든다.
