[백준][Python] 10845. 큐

Silver Ⅳ 🔗10845. 큐

📝문제 요약

문제

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

명령은 총 여섯 가지이다.

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

입력

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

출력

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

✏️문제 풀이

1번 풀이(⌛시간 초과)

• 문제를 너무 그대로 작성해서 시간 초과가 남

    n = int(input())
      
    queue = []
      
    for i in range(n):
        command = input().split()
      
        if command[0] == "push":
            queue.append(command[1])
        elif command[0] == "pop":
            if len(queue) == 0 :
                print(-1)
            else :
                print(queue[0])
                queue.pop(0)
        elif command[0] == 'size':
            print(len(queue))
        elif command[0] == 'empty':
            if queue :
                print(0)
            else :
                print(1)
        elif command[0] == 'front':
            if len(queue) == 0 :
                print(-1)
            else :
                print(queue[0])
        elif command[0] == 'back':
            if len(queue) == 0 :
                print(-1)
            else :
                print(queue[-1])
  

• 해결방법

  • 시간 복잡도를 줄이기 위하여 deque를 사용하고, 입력의 시간을 줄이기 위해 sys.stdin.readline() 사용

최종 풀이

• 사용할 라이브러리 sys와 deque를 불러옴
• 명령어의 개수 n 입력
• 양방향 큐 queue 초기화
• n개의 명령어를 처리
  • 명령어를 입력받아 command에 저장(공백을 기준으로 구분)
    • 시간을 줄이기 위하여 sys.stdin.readline() 사용
  • 입력이 push X : 정수 X를 큐에 넣음
  • 입력이 pop
    • 큐가 비어있으면 -1 출력
    • 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력
  • 입력이 size : 큐에 들어있는 정수의 개수(len(queue))를 출력
  • 입력이 empty : 큐가 비어있으면 1, 아니면 0을 출력
  • 입력이 front: 큐의 가장 앞에 있는 정수를 출력, 큐가 비어있으면 -1 출력
  • 입력이 back: 큐의 가장 뒤에 있는 정수를 출력, 큐가 비어있으면 -1 출력

코드와 함께 보는 풀이

import sys
from collections import deque

# 명령어의 개수 n 입력
n = int(sys.stdin.readline())

# 양방향 큐 초기화
queue = deque()

# n개의 명령어를 처리
for i in range(n):
		# 명령어를 입력받아 command에 저장(공백을 기준으로 구분)
    command = sys.stdin.readline().split()
		
		# 입력이 push X : 정수 X를 큐에 넣음
    if command[0] == "push":
        queue.append(command[1])
        
    # 입력이 pop
    elif command[0] == "pop":
		    # 큐가 비어있으면 -1 출력
        if not queue:
            print(-1)
        # 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력
        else:
            print(queue.popleft())
            
    # 입력이 size : 큐에 들어있는 정수의 개수(len(queue))를 출력
    elif command[0] == 'size':
        print(len(queue))
    
    # 입력이 empty : 큐가 비어있으면 1, 아니면 0을 출력
    elif command[0] == 'empty':
        print(1 if not queue else 0)
    
    # 입력이 front: 큐의 가장 앞에 있는 정수를 출력, 큐가 비어있으면 -1 출력
    elif command[0] == 'front':
        print(queue[0] if queue else -1)
    
    # 입력이 back: 큐의 가장 뒤에 있는 정수를 출력, 큐가 비어있으면 -1 출력
    elif command[0] == 'back':
        print(queue[-1] if queue else -1)

💯제출 코드

import sys
from collections import deque

n = int(sys.stdin.readline())

queue = deque()

for i in range(n):
    command = sys.stdin.readline().split()

    if command[0] == "push":
        queue.append(command[1])
    elif command[0] == "pop":
        if not queue:
            print(-1)
        else:
            print(queue.popleft())
    elif command[0] == 'size':
        print(len(queue))
    elif command[0] == 'empty':
        print(1 if not queue else 0)
    elif command[0] == 'front':
        print(queue[0] if queue else -1)
    elif command[0] == 'back':
        print(queue[-1] if queue else -1)