[백준/Python] 12789 도키도키 간식드리미

문제: https://www.acmicpc.net/problem/12789

 

 

사용 알고리즘: 스택

 

 

입력

• 첫째 줄에는 승환이 앞에 서 있는 학생들의 수 N (1 <= N <= 1,000)
• 승환이 앞에 서있는 모든 학생들의 번호표 (1, 2, 3, ..., N)

 

입력으로 주어진 학생들의 번호표를 올바른 순서로 만들 수 있는지 확인하는 문제 -> 스택을 사용해서 넣고 빼야겠다

 

 

대기번호 순서대로 간식 받게 하기

stack = deque()
waitingNum = 1 # 간식을 받을 차례의 대기번호

for x in arr:
    stack.append(x)
    while stack and stack[-1] == waitingNum: # 빈 스택이 아니고 & 스택 맨 위랑 대기번호가 같을 때
        stack.pop()
        waitingNum += 1 # 대기번호 증가시켜주기

 

주어진 배열의 숫자들을 차례로 스택에 넣어주고,

스택의 맨 위에 있는 숫자와 간식을 받을 차례의 대기번호를 비교해서 두 수가 같다면 -> pop

 

여기서 중요한 건 빈 스택이 아닐 때만 while 문을 돌게 하는 것이다. (이거 때문에 한번 틀렸다)

나는 처음에 while 문에 들어가기 전에 스택에 숫자를 넣어주는데 어떻게 빈 스택이라고 에러가 날 수 있지? 라는 바보같은 생각을 했다

 

입력 아래와 같은 완전 단순한 경우를 생각해보면, 

1을 스택에 추가하고 waitingNum 과 스택 맨 위에 있는 숫자를 비교해서 같으니 pop

그리고 while 문을 나가는 것이 아니라 다시 while 문의 조건문 확인 -> stack[-1] 을 보려고 하는데 빈 스택이니 에러남!

1
1

 

 

대기번호를 순서대로 만들 수 있다면 스택이 비어있을 것이고, 아니라면 스택에 숫자가 남아있을 것이기 때문에 빈 스택인지 확인 후

경우에 맞게 Nice / Sad 출력

if len(stack) == 0: # 빈 스택이라면 Nice
    print('Nice')
else: # 아니라면 Sad
    print('Sad')

 

 

 

전체 코드

import sys
from collections import deque
input = sys.stdin.readline

# 입력
n = int(input())
arr = list(map(int, input().split()))

stack = deque()
waitingNum = 1

stack = deque()
waitingNum = 1 # 간식을 받을 차례의 대기번호

for x in arr:
    stack.append(x)
    while stack and stack[-1] == waitingNum: # 빈 스택이 아니고 & 스택 맨 위랑 대기번호가 같을 때
        stack.pop()
        waitingNum += 1 # 대기번호 증가시켜주기

if len(stack) == 0: # 빈 스택이라면 Nice
    print('Nice')
else: # 아니라면 Sad
    print('Sad')