[백준][10845][Silver 4] - 큐 python

1. [Silver IV] 큐 - 10845

10845번: 큐

1.0.1. 성능 요약

메모리: 31256 KB, 시간: 52 ms

1.0.2. 분류

자료 구조, 큐

1.0.3. 문제 설명

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

명령은 총 여섯 가지이다.

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

1.0.4. 입력

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

1.0.5. 출력

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

 

---

1.1. 🙋 문제 해석

유명한 자료구조의 큐문제입니다. 문제이기에 풀었지만 리스트로 구현한 큐의 단점은 큐의 맨 앞 원소를 삭제하고자 할 때 모든 원소를 앞으로 옮겨야 하는 단점이 있습니다. 이러한 단점은 큐의 원소가 많아질수록 성능 저하를 가져올 수 있습니다. 이를 보완하기 위해서는 collections 모듈에서 제공하는 deque(덱)을 주로 사용합니다.

1.1.1. 🔑 Solution 🔑

      

      

      

    
    

      <code />
    
from sys import stdin
T = int(stdin.readline())
que=[]
for i in range(T):
    A = list(stdin.readline().split())
    if A[0] == 'push' :
        que.append(A[1])

• 입력받고 push처리는 배열로나누어처리했습니다.

  
        
  
        
  
        
  
      
      
  
        <code />
      
    elif A[0] == 'pop' :
        if len(que)!=0 :
            print(que[0])
            que.pop(0)

  원소 삭제 방법
• 원소를 삭제할 때 del que[0]를 사용해도 되는데, 인덱스를 이용한 삭제 방법은 오류 생길 가능성이 있습니다 que.pop(0)과 같이 pop 메서드를 사용하는 것이 낫습니다.

      

      

      

    
    

      <code />
    
        else :
            print(-1)
    elif A[0] == 'empty' :
        if len(que)==0 :
            print(1)
        else :
            print(0)
    elif A[0] == 'size' :
        print(len(que))
    elif A[0] == 'front' :
        if len(que) == 0 :
            print(-1)
        else :
            print(que[0])

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

1.1.1.1. 🕐 시간 복잡도

• 리스트로 구현한 큐에서는 pop(0)과 같은 메서드를 사용할 때마다 리스트의 원소들을 모두 앞으로 당겨와야 하므로, 시간 복잡도가 O(n)입니다. 따라서, 큐의 길이가 길어지면 성능 저하를 일으킬 수 있습니다.
• 다시말하자면 이러한 경우에는 deque와 같은 다른 자료구조를 사용하는 것이 좋습니다.