[Python] 백준 Stack/Queue/Deck 문제 풀이 팁(tip) 정리

Stack: 10828, 9012, 10799
Queue: 10845
Deck: 10866 

---

~ 목차 ~

 

STACK
1. import deque from collections
2. stack이 비어있는지 확인
3. 기본 동작들을 list로 구현하기

* boj.kr/10799 쇠막대기 *

 

QUEUE ( 백준 10845 )

1. stack과 다른 점

DEQUE ( 백준 10866 )

1. stack, queue와 다른 점

---

STACK

1. import deque from collections

Deque is preferred over list in the cases where we need quicker append and pop operations from both the ends of the container, as deque provides an O(1) time complexity for append and pop operations as compared to list which provides O(n) time complexity. 

 

 기본 list와 동일하게 append, pop을 사용할 수 있다. 하지만 list는 O(N)의 시간 복잡도, depue는 O(1)의 시간복잡도 이므로 시간 초과가 생기는 등의 경우에 

stack=deque()를 사용한다.

 

2. stack이 비어있는지 확인

if(not stack):

 

3. 기본 동작들을 list로 구현하기

- push: append

- pop: print( list.pop() )

- size: len

- top: list[-1]

 

* boj.kr/10799 쇠막대기 *

아이디어: 스택을 사용하는건 생각하기 쉬우나, 레이저가 나타날 때마다 막대수를 더하는 게 어렵다. '(' 의 갯수만큼 더하고 ')' 나올때마다 +1 한다.

---

QUEUE ( 백준 10845 )

1. stack과 다른 점

- 둘다 list로 구현할 수 있으나 append대신 insert(0, number)을 사용해서 먼저 삽입한 값이 뒤로 가도록 차례로 밀어준다.

 

* attributeError: 없는 메소드를 썼을 때(자꾸 오타가 난다.. 유의! )

import sys
n=int(sys.stdin.readline().rstrip())
queue=[]

for _ in range(n):
    input=sys.stdin.readline().rstrip().split()
    mention=input[0]
    
    if mention=="push":
        queue.insert(0,input[1])
        
    elif mention=="pop":
        if(not queue):
            print(-1)
        else:
            print(queue.pop())
            
    elif mention=="size":
        print(len(queue))
        
    elif mention=="empty":
        if (not queue):
            print(1)
        else:
            print(0)
            
    elif mention=="front":
        if(not queue):
            print(-1)
        else:
            print(queue[-1])
            
    elif mention=="back":
        if(not queue):
            print(-1)
        else:
            print(queue[0])

---

DEQUE ( 백준 10866 )

1. stack, queue와 다른 점

- 셋다 list로 구현할 수 있으나 pop할 때 deque.pop(0) 로 인덱스를 지정해서 pop_back을 처리해준다.

import sys

n=int(sys.stdin.readline().rstrip())
deque=[]

for _ in range(n):
    input=sys.stdin.readline().rstrip().split()
    mention=input[0]
    
    if mention=="push_front":
        deque.append(input[1])
        
    elif mention=="push_back":
        deque.insert(0,input[1])
        
    elif mention=="pop_front":
        if (not deque):
            print(-1)
        else:
            print(deque.pop())
            
    elif mention=="pop_back":
        if (not deque):
            print(-1)
        else:
            print(deque.pop(0))
            
    elif mention=="size":
        print(len(deque))
        
    elif mention=="empty":
        if (not deque):
            print(1)
        else:
            print(0)
            
    elif mention=="front":
        if (not deque):
            print(-1)
        else:
            print(deque[-1])
            
    elif mention=="back":
        if (not deque):
            print(-1)
        else:
            print(deque[0])

 

 

 

소통하고 싶은 내용이 있으면 언제든 댓글주세요.