[알고리즘] 백준 18258 큐 2

문제링크

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

문제 설명

• 큐 구현하기

주제

• 큐, 덱

난이도

• 하

풀이 전 생각한 것

1. Linked List를 이용하여 큐를 구현하기

1차 풀이 (선형 탐색)

import sys

class Node:
    def __init__(self, value):
        self.data = value
        self.next = None


class Queue:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0

    # 맨뒤에 데이터 추가
    def push(self, value):
        new_node = Node(value)
        if self.is_empty():
            self.head = new_node
        else:
            # 왜 self.tail.next에도 노드를 추가할까?
            self.tail.next = new_node
        self.size += 1
        self.tail = new_node

    def pop(self):
        if self.is_empty():
            return -1

        temp = self.head
        self.head = self.head.next
        self.size -= 1
        return temp.data

    def get_size(self):
        return self.size

    def is_empty(self):
        return 1 if self.head is None else 0

    def front(self):
        if self.is_empty():
            return -1
        return self.head.data

    def back(self):
        if self.is_empty():
            return -1
        return self.tail.data


n = int(input())
queue = Queue()

for _ in range(n):
    msg = list(sys.stdin.readline().split())

    if msg[0] == 'push':
        queue.push(msg[1])
    elif msg[0] == 'pop':
        print(queue.pop())
    elif msg[0] == 'size':
        print(queue.get_size())
    elif msg[0] == 'empty':
        print(queue.is_empty())
    elif msg[0] == 'front':
        print(queue.front())
    elif msg[0] == 'back':
        print(queue.back())

풀이 방법

• Linked List로 생성한 큐를 구현하였다.

문제를 풀고 알게된 개념 및 소감

• 큐의 기본적인 이론만 가지고 있으면 풀 수 있는 간단한 문제라고 생각했지만..시간 초과로 인해 바로 통과하지는 못했다. 전에는 시간 초과가 그냥 화나기만 했는데 이제는 코드를 시간적인 측면으로 더 효율적이게 만들어준다구..긍정적으로 생각하련다