백준 18258 - 큐 2

https://www.acmicpc.net/problem/18258

18258번: 큐 2

 

 

 

 

이 문제는 단순히 큐에 대한 문제이다.

그래서 큐를 열심히 구현했는데 시간초과가 나왔다.

아래 코드는 시간초과가 나온 코드이다.

 

class MyQueue:
    def __init__(self):
        self.myQueue = []

    def push(self, n):
        self.myQueue.append(n)

    def pop(self):
        if len(self.myQueue)==0:
            return -1
        else:
            tmp = self.myQueue[0]
            del self.myQueue[0]
            return tmp

    def size(self):
        return len(self.myQueue)

    def empty(self):
        if self.size() == 0:
            return 1
        else:
            return 0

    def front(self):
        if self.empty() == 1:
            return -1
        else:
            return self.myQueue[0]

    def back(self):
        if self.empty() == 1:
            return -1
        else:
            return self.myQueue[-1]


import sys
n = int(sys.stdin.readline())
q = MyQueue()
ans = 0

for i in range(n):
    cm = sys.stdin.readline().strip()
    if " " in cm:
        a, b = cm.split()
        b = int(b)
    else:
        a = cm

    if a == 'push':
        q.push(b)
    elif a == 'front':
        ans = q.front()
        print(ans)
    elif a == 'back':
        ans = q.back()
        print(ans)
    elif a == 'size':
        ans = q.size()
        print(ans)
    elif a == 'empty':
        ans = q.empty()
        print(ans)
    elif a == 'pop':
        ans = q.pop()
        print(ans)

 

이렇게 리스트를 활용하여 큐를 구현했는데 아마 pop하는 과정에서 시간복잡도가 O(N)이 되어 시간 초과가 나온 것이라고 생각된다. 이 문제는 큐에 대한 모든 연산을 O(1)의 시간복잡도로 구현해야한다.

 

 

 

그래서 collections에서 deque(데큐)를 임포트해서 구현하였다.

아래 코드는 deque를 사용해서 시간초과가 나오지 않은 코드이다.

 

from collections import deque
import sys

n = int(sys.stdin.readline())
q = deque()
for i in range(n):
    cm = sys.stdin.readline().strip()
    if " " in cm:
        a, b = cm.split()
        b = int(b)
    else:
        a = cm

    if a == 'push':
        q.append(b)
    elif a == 'front':
        if len(q) != 0:
            ans = q[0]
        else:
            ans = -1
        print(ans)
    elif a == 'back':
        if len(q) != 0:
            ans = q[-1]
        else: 
            ans = -1
        print(ans)
    elif a == 'size':
        ans = len(q)
        print(ans)
    elif a == 'empty':
        if len(q) == 0:
            ans = 1
        else:
            ans = 0
        print(ans)
    elif a == 'pop':
        if len(q) != 0:
            ans = q.popleft()
        else:
            ans = -1
        print(ans)

deque를 사용하면 큐에 대한 모든 연산을 O(1)의 시간복잡도로 구현할 수 있다.

 

리스트와 데큐의 시간복잡도 비

 

deque를 사용한 김에 deque에 대한 기본 함수를 알아보도록 하자.

 

데큐는 양쪽에서 삽입과 삭제가 가능한 자료구조이다.

 

아래는 deque에서 제공하는 여러 함수들을 정리한 포스팅이다.

https://cocobi.tistory.com/202  참고할 것