[백준] 12789 파이썬(python) : 도키도키 간식드리미 - (올바른배열인지확인)

12789번: 도키도키 간식드리미

 

 

 

빠져 나갈 수 있는 방법은 단 2가지이다. 줄을 서있는 장소와 대기열에서 빠져나오는것이다. 줄을 서있는 장소는 FIFO이 가능하므로 queue라고 할 수 있고, 대기열은 FILO이므로 스택으로 볼 수 있다.

 

queue의 가장 왼쪽에서 번호표와 일치하면 빠져나갈 수 있고 stack의 top에서 번호표와 일치하면 빠져나갈 수 있다.

 

 

성공적으로 끝나는 경우

 

queue도 stack도 모두 잘 끝내서 종료된 모습이다.

 

 

실패하는 경우

 

 

out_num가 3인데 stack의 top은 4여서 꺼내지 못하고 종료하는 상황이다.

 

 

from collections import deque
import sys
n = int(sys.stdin.readline())
queue = deque(map(int, sys.stdin.readline().split())) #1
stack = [] #2
out_num = 1 #3
while queue:
    if queue[0] == out_num: #4
        queue.popleft()
        out_num += 1
    else: #5
        stack.append(queue.popleft())
    while stack and stack[-1] == out_num: #6
        stack.pop()
        out_num += 1
print('Nice' if not stack else 'Sad') #7

 

 

#1 : 오른쪽으로 입력받아서 왼쪽으로 빠져나올 수 있으므로 deque로 선언

#2 : 대기열을 표현할 stack 선언

#3 : 번호표 순서대로 나가야하므로 1로 초기화

#4 : queue[0]가 원하는 숫자와 같으면 queue에서 빼주고 숫자 +1

#5 : 아니라면 stack에 삽입

#6 : stack이 비어있지 않고 top이 out_num과 같으면 stack.pop()하고 숫자 +1

#7 : 삼항연산자를 이용해서 올바른 배열이면 Nice 아니면 Sad 출력

 

 

올바른 입력값이라고 가정한 후에 코드를 작성하고 마지막 출력에서 stack에 원소가 없으면 모두 다 출력이 된거니까 Nice를 출력하고 stack에 원소가 남아있으면 Sad를 출력한다.

 

 

비슷한 문제

https://hgk5722.tistory.com/250

[백준] 2504 파이썬(python) : 괄호의 값 - (★)