[백준] [Python] 18258번 큐2

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

18258번: 큐 2

 

 

 

Python

class Node:
    def __init__(self, elem, link=None):
        self.data = elem
        self.link = link

class LinkedQueue:
    def __init__(self):
        self.head = None
        self.tail = None
        self.length = 0
        
    def isEmpty(self):
        return self.head == None

    def size(self):
        return self.length

    def push (self, elem):
        self.length += 1
        if self.head == None:
            self.head = self.tail = Node(elem, self.head)
        else:
            self.tail.link = Node(elem, None)
            self.tail = self.tail.link

    def delete(self):
        if self.head is not None:
            self.length -= 1
            x = self.head.data
            if self.head == self.tail:
                 self.head = self.tail = None
            else:
                  self.head = self.head.link
            return x

import sys
input = sys.stdin.readline

q = LinkedQueue()
for _ in range(int(input())):
    cmd = input().split()
    if cmd[0] == "push":
        q.push(int(cmd[1]))
    elif cmd[0] == "pop":
        print( -1 if q.isEmpty() else q.delete())
    elif cmd[0] == "size":
        print(q.size())
    elif cmd[0] == "empty":
        print(  1 if q.isEmpty() else 0 )
    elif cmd[0] == "front":
        print( -1 if q.isEmpty() else q.head.data)
    elif cmd[0] == "back":
        print( -1 if q.isEmpty() else q.tail.data)
        

 

 

 

풀이

연결리스트로 풀게 되면 link와 data를 동시에 각각의 변수가 가져야 하기에 메모리를 많이 차지하게 된다.

대신 삽입과 삭제에 있어 O(1)의 시간으로 마칠 수 있기 때문에 

시간 제한이 타이트하고 메모리를 넉넉하게 주는 문제라면 연결리스트로 풀 수 있다

 

전체 길이를 구하는 함수는 넣고 뺄 때마다 그 길이의 변화를 반영하는 식으로 하여

하나씩 스캔하여 전체 길이를 구하는 일이 없도록 하였다.