[백준 28279번] 덱 2 - Python, 덱 주요 메서드/시간 복잡도

문제

28279번: 덱 2

---

풀이

import sys
from collections import deque

input = sys.stdin.readline

deq = deque()

N = int(input())

for _ in range(N):
    order = list(map(int, input().split()))
    if order[0] == 1:
        deq.appendleft(order[1])
    elif order[0] == 2:
        deq.append(order[1])
    elif order[0] == 3:
        if (deq):
            print(deq.popleft())
        else:
            print(-1)
    elif order[0] == 4:
        if (deq):
            print(deq.pop())
        else:
            print(-1)
    elif order[0] == 5:
        print(len(deq))
    elif order[0] == 6:
        if (deq):
            print(0)
        else:
            print(1)
    elif order[0] == 7:
        if (deq):
            print(deq[0])
        else:
            print(-1)
    elif order[0] == 8:
        if (deq):
            print(deq[-1])
        else:
            print(-1)

 

아이디어

3: 덱에 정수가 있다면 맨 앞의 정수를 빼고 출력한다. 없다면 -1을 대신 출력한다. -> 이 말이 맨 앞 정수를 빼고 리스트를 출력하라는 말로 처음에 잘못 이해를 했는데 그냥 정수를 빼고 말 그대로 그 정수를 출력하면 된다.

 

 

✏️ deque의 메서드를 잘 알면 풀 수 있는 문제

Python의 deque 클래스는 내장 데이터 구조 중 하나로, 양쪽 끝에서 빠르게 추가 및 제거할 수 있는 큐(Deque)를 구현

 

넣기, 빼기 - O(1)

- appendleft(): 앞에 넣기

- append(): 뒤에 넣기

- pop(): 맨 뒤 하나 빼고 그 값 반환

- popleft(): 맨 앞 하나 빼고 그 값 반환

 

길이, 처음/마지막 - O(1)

- len(deque): deque 길이 

- deque[0]: 첫번째 원소

- deque[-1]: 마지막 원소

 

추가 알면 좋은 메서드 - O(N)

- index(x): x의 첫번째 등장 인덱스 반환, 없으면 ValueError

- index(x, idx, idx+3): x를 idx부터 idx+3(포함 x)까지 검색해 찾은 첫번째 인덱스 반환

- deque.count(x) -> deque 내의 x의 개수

- deque.remove(x) -> 첫 번째 x 지우기

- deque.clear() -> 모든 요소 제거

- deque.insert(idx, x) -> idx에 x 삽입

- deque.reverse() -> deque 뒤집기

 

추가 알면 좋은 메서드 - O(K)_k는 iterable에 포함된 요소에 개수

- deque.extend([4, 5, 6]) -> 뒤에 4, 5, 6 추가

- deque.extendleft([4, 5, 6]) -> 앞에 4, 5, 6 추가

- deque.rotate(-3) ->

deque([9, 8, 7, 1, 2, 3, 4, 5, 6])

⬇️

deque([1, 2, 3, 4, 5, 6, 9, 8, 7])

뒤로 3칸식 이동

---

참고

https://www.geeksforgeeks.org/deque-in-python/

 

 

 

🙂 공부하면 정리하는 글입니다. 잘못된 점이 있다면 피드백 남겨주시면 감사합니다.