[백준] #28278 (스택2), #18258 (큐2)

#28278

input으로 받았더니 시간 초과가 나서 sys.stdin.readline()으로 받았다.

import sys

class Stack:
    def __init__(self):
        self.listStack = []
    
    def push(self, x): #1
        self.listStack.append(x)
    
    def pop(self): #2
        print(int(self.listStack.pop()) if self.listStack else -1)
        
    def lenStack(self): #3
        print(len(self.listStack))
        
    def printisEmpty(self): #4
       if len(self.listStack) == 0: print(1)
       else: print(0)
    
    def top(self): #5
        print(int(self.listStack[-1]) if self.listStack else -1)

N = int(sys.stdin.readline().strip())
astack = Stack()

for _ in range(N):
    a = sys.stdin.readline().split()
    if len(a) > 1:
        astack.push(a[1])
    if a[0] == '2':
        astack.pop()
    if a[0] == '3':
        astack.lenStack()
    if a[0] == '4':
        astack.printisEmpty()
    if a[0] == '5':
        astack.top()

---

#18258

처음엔 이렇게 풀었으나 시간초과...
pop이 O(n)의 시간복잡도를 가지기 때문이라고.
연결 리스트를 사용해서 풀어야 한다고 한다.

import sys

class Queue:
    def __init__(self):
        self.listQueue = []
    def push(self,x):
        self.listQueue.append(x)
    def pop(self):
        print(int(self.listQueue.pop(0)) if self.listQueue else -1)
    def size(self):
        print(len(self.listQueue))
    def empty(self):
        print(0 if self.listQueue else 1)
    def front(self):
        print(self.listQueue[0] if self.listQueue else -1)
    def back(self):
        print(self.listQueue[-1] if self.listQueue else -1)
    
    
N = int(sys.stdin.readline().strip())
aqueue = Queue()

for _ in range(N):
    a = sys.stdin.readline().split()
    if len(a) > 1:
        aqueue.push(a[1])
    if a[0] == 'pop':
        aqueue.pop()
    if a[0] == 'size':
        aqueue.size()
    if a[0] == 'empty':
        aqueue.empty()
    if a[0] == 'front':
        aqueue.front()
    if a[0] == 'back':
        aqueue.back()

찾아보니 파이썬에서는 연결 리스트로 구성되어 있는 collection.deque(), 데크를 사용하면 훨씬 효율적이라고 한다. 데크를 사용하면 동 문제에 대해 O(1)의 시간복잡도로 문제를 해결할 수 있음.

아래는 deque를 상속받은 Queue 클래스 사용해 해결한 코드.

import sys
from collections import deque

class Queue(deque):
    def push(self, x):
        self.append(x)

    def pop(self):
        print(int(super().popleft()) if self else -1)

    def size(self):
        print(len(self))

    def empty(self):
        print(0 if self else 1)

    def front(self):
        print(self[0] if self else -1)

    def back(self):
        print(self[-1] if self else -1)

N = int(sys.stdin.readline().strip())
aqueue = Queue()

for _ in range(N):
    a = sys.stdin.readline().split()
    if len(a) > 1:
        aqueue.push(a[1])
    if a[0] == 'pop':
        aqueue.pop()
    if a[0] == 'size':
        aqueue.size()
    if a[0] == 'empty':
        aqueue.empty()
    if a[0] == 'front':
        aqueue.front()
    if a[0] == 'back':
        aqueue.back()