[자료구조] [BJ10866] 덱

코드 플러스

🚩 문제 설명

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

10866번: 덱

BJ10866

 

⏱️ 시간 복잡도
▪ 총 명령어의 수는 N개 이다.
▪ 시간복잡도는 대략적으로 O(N)이라고 할 수 있다.

◾ 스택이나 큐 문제 처럼 덱을 구현해서 명령을 처리하여 결과값을 출력하는 문제

◾ 명령어 8가지

• push_front X : 정수 X를 덱의 앞에 넣는다.
• push_back X : 정수 X를 덱의 뒤에 넣는다.
• pop_front : 덱의 가장 앞에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• pop_back : 덱의 가장 뒤에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size : 덱에 들어있는 정수의 개수를 출력한다.
• empty : 덱이 비어있으면 1을, 아니면 0을 출력한다.
• front : 덱의 가장 앞에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• back : 덱의 가장 뒤에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다

 

 

 

---

 

 

 

✅ 입출력

1) N : 명령어의 수
2) 두번째 줄부터 명령어들이 주어진다.
return ➡️ 명령어에 따른 결과값을 출력

✔️ 예제 1

15
push_back 1
push_front 2
front
back
size
empty
pop_front
pop_back
pop_front
size
empty
pop_back
push_front 3
empty
front

2
1
2
0
2
1
-1
0
1
-1
0
3

 

✔️ 예제 2

22
front
back
pop_front
pop_back
push_front 1
front
pop_back
push_back 2
back
pop_front
push_front 10
push_front 333
front
back
pop_back
pop_back
push_back 20
push_back 1234
front
back
pop_back
pop_back

-1
-1
-1
-1
1
1
2
2
333
10
10
333
20
1234
1234
20

 

 

 

---

 

 

 

📑 문제 풀이

with 파이썬 (Python)

import sys
from collections import deque

N = int(sys.stdin.readline())  # 명령어의 수
coms = [sys.stdin.readline().strip() for _ in range(N)]
que = deque([])

for com in coms:
    splited = com.split()

    if splited[0] == 'push_back':
        que.append(splited[1])

    elif splited[0] == 'push_front':
        que.appendleft(splited[1])

    elif splited[0] == 'pop_back':
        if que:
            print(que.pop())
        else:
            print(-1)

    elif splited[0] == 'pop_front':
        if que:
            print(que.popleft())
        else:
            print(-1)

    elif splited[0] == 'size':
        print(len(que))

    elif splited[0] == 'empty':
        if que:
            print(0)
        else:
            print(1)

    elif splited[0] == 'back':
        if que:
            print(que[-1])
        else:
            print(-1)

    elif splited[0] == 'front':
        if que:
            print(que[0])
        else:
            print(-1)

💬 Point

➡️  from collections import deque 사용

◾ 파이썬에서 deque을 사용하면 덱을 구현할 수 있다.

◾ 왼쪽이 front고 오른쪽이 back이니 유의하시길 바란다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

➕ 참고

https://yeomss.tistory.com/106?category=985840 

[자료구조] [BJ10845] 큐

 

# 코드플러스 덱 파이썬

# 백준 11866 덱 파이썬

---