[백준] 큐(10845) - 파이썬(Python)

🔗 문제 링크

---

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

 

문제 설명

정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

주어진 명령

- push X: 정수 X를 큐에 넣는 연산이다.
- pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
- size: 큐에 들어있는 정수의 개수를 출력한다.
- empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
- front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
- back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

- 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 
- 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 
- 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 
- 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

- 출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

 

✨ 풀이 과정

---

💡이 문제는 큐를 이용해서 문제에 주어진 지시대로 코드를 작성하면 쉽게 해결할 수 있는 문제이다.

📖 내가 작성한 풀이 방법

1. 명령의 수 N을 선언한다.
2. 정수를 저장하는 큐인 command_queue를 선언한다.
3. N번 반복하면서 각각의 명령들을 주어진 지문대로 수행한다.

⬇️ 반복문 부분      
- 명령의 첫 번째 요소가 push인 경우 → 정수 X를 `command_queue=[]`에 추가한다.
- 명령의 첫 번째 요소가 pop인 경우 → `pop(0)`을 이용해서 가장 앞에 있는 정수를 출력한다. 정수가 없을 경우 -1을 출력한다.
- 명령의 첫 번째 요소가 size인 경우 → 큐에 들어있는 정수의 개수를 `len()`을 이용해서 출력한다.
- 명령의 첫 번째 요소가 empty인 경우 → 큐가 비어있으면 1, 아니면 0을 출력한다.
- 명령의 첫 번째 요소가 front인 경우 → 큐의 가장 앞에 있는 정수를 출력하고, 없는 경우에는 -1을 출력한다.
- 명령의 첫 번째 요소가 back인 경우 → 큐의 가장 뒤에 있는 정수를 출력하고, 없는 경우에는 -1을 출력한다.

👩‍💻 최종 코드

---

# 명령의 수 N을 선언한다.
N=int(input())

# 정수를 저장하는 큐를 선언한다.
command_queue=[]

# N번 반복하면서 각 명령들을 수행한다.
for _ in range(N):
    # 명령을 입력받을 리스트를 선언한다.
    command=input().rstrip().split() 
    # 명령의 첫번째 요소가 push이면 해당 문을 수행한다.
    if command[0]=="push":
        command_queue.append(command[1])
    # 명령의 첫번째 요소가 pop이면 해당 문을 수행한다.
    elif command[0]=="pop":
        print(command_queue.pop(0) if command_queue else -1)
    # 명령의 첫번째 요소가 size이면 해당 문을 수행한다.
    elif command[0]=="size":
        print(len(command_queue))
    # 명령의 첫번째 요소가 empty이면 해당 문을 수행한다.
    elif command[0]=="empty":
        print(0 if command_queue else 1)
    # 명령의 첫번째 요소가 front이면 해당 문을 수행한다. 
    elif command[0]=="front":
        print(command_queue[0] if command_queue else -1)
    # 명령의 첫번째 요소가 back이면 해당 문을 수행한다. 
    elif command[0]=="back":
        print(command_queue[-1] if command_queue else -1)

📖 다른 풀이 방법

💡`deque`를 사용해서 작성하는 방법도 있다.
→ deque: 양방향에서 데이터 추가/제거할 수 있는 자료구조이다.

✅`deque`를 사용하는 경우에 append,pop같은 list는 시간복잡도가 O(n)이지만, `deque`는 O(1)이기 때문에 `deque`가 더 효율적이라고 볼 수 있다.

 

👩‍💻 deque를 이용한 최종 코드

---

import sys
from collections import deque

deq=deque()

N=int(input())

for _ in range(N):
    cmd=sys.stdin.readline().strip().split()

    if cmd[0]=='push':
        deq.append(int(cmd[1]))

    elif cmd[0]=='pop':
        try:
            # popleft(): 맨 왼쪽값을 돌려주고 리스트에서 삭제
            print(deq.popleft())
        except:
            print(-1)
 
    elif cmd[0]=='size':
        print(len(deq))

    elif cmd[0]=='empty':
        if deq:
            print(0)
        else:
            print(1)

    elif cmd[0]=='front':
        try:
            print(deq[0])
        except:
            print(-1)

    elif cmd[0]=='back':
        try:
            print(deq[-1])
        except:
            print(-1)