백준

[백준 10845] 큐

종식당 2024. 1. 17. 18:00
728x90
반응형

 

c++에서 STL을 이용하여 큐를 접했지만 파이썬에서는 큐를 처음 이용한 것 같아 글을 써보려 한다.

먼저 파이썬에서 큐를 구현하는 방법은 list, deque, Queue 총 3가지가 있다.

 

  • list
q = [1,2,3,4,5]
q.append(6)
q.append(7)
print(q)

 

---> 출력 : [1, 2, 3, 4, 5, 6, 7]

리스트로 구현했으므로 기존에 리스트에 원소를 추가하는 방식처럼 append를 이용하면 된다.

 

q = [1,2,3,4,5]
q.insert(0,10)

 

---> 출력 : [10, 1, 2, 3, 4, 5]

insert(인덱스, 값)를 통해 원하는 인덱스 위치에 추가할 수도 있다.

print(q.pop())
print(q)

 

---> 출력 : 7
                [1, 2, 3, 4, 5, 6]

q.pop()을 통해 마지막 원소를 삭제할 수 있고 삭제한 원소와 삭제 후 리스트를 위에서 확인할 수 있다.

q.pop(인덱스)를 통해 원하는 인덱스에 저장되어 있는 값을 삭제할 수 도 있다.

 

list를 통해 큐를 충분히 구현할 수 있지만 이 방법은 성능 측면에서 좋지 않다. 위 연산에서 pop(인덱스), insert(인덱스, 값)의 시간 복잡도는 O(n)이기 때문에 데이터가 많아지면 느려질 수밖에 없다.

 

  • deque

두 번째 방법은 deque(덱)이다. double ended queue의 약자로서 데이터를 양방향에서 추가하고 삭제할 수 있다.

이를 사용하기 위해서는 먼저 from collections import deque를 진행해야 한다. -> collections모듈에서 deque클래스 사용

from collections import deque
q = deque([1,2,3,4])
q.append(5)
q.appendleft(10)

print(q)

q.popleft()
print(q)

 

---> 출력 : deque([10, 1, 2, 3, 4, 5])
                 deque([1, 2, 3, 4, 5])

deque에서는 appendleft()와 popleft()를 사용할 수 있다. 단어에서 볼 수 있듯이 가장 왼쪽에 추가하고 가장 왼쪽의 값을 제거할 수 있다. 이 두 메서드 모두 O(1)의 시간 복잡도를 가지기 때문에 list로 구현할 때 보다 훨씬 더 빠르다.

하지만 random access에서 시간 복잡도가 O(n)이고 내부적으로 linked list를 사용하기 때문에 i번째 데이터에 접근하기 위해서는 i번 순회해야 해서 성능 면에서 떨어진다.

 

  • Queue

마지막 방법은 Queue를 사용하는 방법이다. 주로 멀티 쓰레딩 환경에서 사용되며, 내부적으로 locking을 지원하여 여러 개의 스레드가 동시에 데이터를 추가하거나 삭제할 수도 있다고 한다.

from queue import Queue
q = Queue()
q.put(1)
q.put(2)
q.put(3)

print(q)
print(q.get())
print(q.get())
print(not q.full())
print(q.empty())

 

---> 출력 :<queue.Queue object at 0x0000018 F820 BBFD0>

                 1
                 2
                 True
                 False

 

Queue를 이용하면 큐에 push 할 때 put()을 사용하면 되고 get()을 통해 먼저 들어온 값을 얻을 수 있다. full()과 empty()를 통해 큐의 상태 또한 확인할 수 있으니 알아두자. q.qsize()로 큐의 사이즈도 알 수 있다!

 

queue 라이브러리에는 다양한 큐 구조로 Queue(), LifoQueue(), PriorityQueue()를 제공한다.
프로그램을 작성할 때 프로그램에 따라 적합한 자료 구조를 사용하면 된다.


Queue() : 가장 일반적인 큐 자료구조 -> q = q.Queue()
LifoQueue() : 나중에 입력된 데이터가 먼저 출력되는 구조(스택 구조라고 보면 됨) -> q = q.LifoQueue()
PriorityQueue() : 데이터마다 우선순위를 넣어, 우선순위가 높은 순으로 데이터 출력 -> q = q.PriorityQueue()

 

위에서 간단하게 파이썬에서의 큐에 대해서 알아보았고 다음에 이번 문제의 코드이다.

import sys

input = sys.stdin.readline

N = int(input())

q = []

for i in range(N):
    lst = input().split()
    
    if lst[0] == "push":
        q.insert(0,lst[1])
    elif lst[0] == "front":
        if len(q) == 0: print(-1)
        else: print(q[-1])
    elif lst[0] == "back":
        if len(q) == 0: print(-1)
        else: print(q[0])
    elif lst[0] == "size":
        print(len(q))
    elif lst[0] == "pop":
        if len(q) == 0: print(-1)
        else: print(q.pop())
    elif lst[0] == "empty":
        if len(q) == 0: print(1)
        else: print(0)

 

간단하게 list를 이용하여 큐를 구현하여 문제를 풀어보았다.

 

728x90
반응형