[18258] 큐 2 / 파이썬

문제

시간제한 / 메모리 제한

입/출력

예제

알고리즘 분류

풀이

• 리스트를 이용해서 que를 구현했다.
• 문제의 조건에 따라 그대로 코드를 쳤다.
• 아 ㅋㅋ개쉽네 제출
• 결과 :

• pop(0) 부분이 문제였다.
• collections 라이브러리의 deque를 사용해서 pop(0) 대신 popleft() 메서드를 사용하였다.
• 통과!

 

코드

from collections import deque
import sys
input = sys.stdin.readline
que = deque()
N = int(input())
for _ in range(N):
    order = input()
    if order[:2] == "pu":
        push, num = order.split()
        que.append(int(num))
        continue
    elif order[:2] == "po":
        if que:
            print(que.popleft())
        else:
            print(-1)
        continue
    elif order[0] == "s":
        print(len(que))
        continue
    elif order[0] == "e":
        if que:
            print(0)
        else:
            print(1)
        continue
    elif order[0] == "f":
        if que:
            print(que[0])
        else:
            print(-1)
        continue
    elif order[0] == "b":
        if que:
            print(que[-1])
        else:
            print(-1)
        continue

 

새로 알게 된 점

파이썬에서 queue를 구현할 수 있는 방법은 세 가지가 있다.

1. 리스트로 queue 구현

하지만 파이썬의 list는 무작위 접근에 최적화된 자료 구조이기 때문에 pop이나 insert는 성능적으로 불리하다.

시간 복잡도가 O(n)이기 때문에 담고 있는 데이터의 개수가 많아질수록 느려진다.

첫 번째 데이터를 제거하거나 추가하면 그 뒤에 있는 모든 데이터들을 한칸씩 당겨주거나 밀어주어야 하기 때문이다. 그래야 queue[i] 값이 정확함

2. from collections import deque

collections모듈에서 제공하는 deque는 popleft, appendleft같은 메서드를 제공하여 양방향에서 데이터를 추가하고 제거할 수 있다. 이 메서드들은 모두 O(1)의 시간 복잡도를 가지기 때문에 pop()이나 insert()보다 성능이 좋다.

대신 deque는 무작위 접근에 대해서는 O(n)의 시간 복잡도를 가진다. 내부적으로 linked list를 사용하기 때문에 i번째 데이터에 접근하기 위해서는 맨 앞/뒤부터 i번 순회가 필요하기 때문이다.

3.  queue모듈의 Queue클래스

이 방법은 주로 *멀티 쓰레딩 환경에서 사용하고, 내부적으로 **라킹을 지원하여 여러 개의 쓰레드가 동시에 데이터를 추가하거나 삭제할 수 있다.

list, deque와의 차이점은 방향성이 없다는 것이다. 때문에 데이터 추가와 삭제가 하나의 메서드로 처리된다.

데이터를 추가하려면 put(x), 삭제하려면 get() 메서드를 쓰면 된다.

deque처럼 O(1)의 성능을 가지는데 인덱스 접근은 지원하지 않는다.

 

*멀티쓰레드(multi thread): 하나의 프로세스 내에서 둘 이상의 스레드가 동시에 작업을 수행하는 것

**라킹(locking): 둘 이상의 트랜잭션이 공통 데이터에 대해 동시에 접근하지 못하게 잠그는 것

출처: https://www.daleseo.com/python-queue/