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

백준 #12789 도키도키 간식드리미

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

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

n = int(input())   # 학생 수
num = deque(list(map(int, input().split())))   # 번호표

now = 1   # 현재 받아야 하는 번호
q = []   # 빈 공간

while num:
  if now == num[0]:
    num.popleft()
    now += 1
  elif len(q) != 0 and now == q[-1]:
    q.pop()
    now += 1
  else:
    if len(q) == 0 or (len(q) != 0 and q[-1] > num[0]):
      q.append(num.popleft())
    else:
      print("Sad")
      exit(0)

if len(q) != 0:
  for i in range(len(q)-1, -1, -1):
    if now == q[i]:
      now += 1
    else:
      print("Sad")
      exit(0)
  
print("Nice")

1. 현재 간식을 받아야 하는 사람의 번호를 변수(now)에 담아둔다.
2. 순서대로 간식줄(num) 맨 앞에 있는 사람이 해당 번호와 같다면 간식을 배부하고 간식줄에서 뺀다.
3. 같지 않을 경우 빈 공간(q) 마지막에 있는 사람의 번호와 같은지 비교한다. 같다면 간식을 배부하고 빈 공간에서 뺀다.
4. 즉, 간식줄 맨 앞 혹은 빈 공간 맨 뒤에 있는 사람이 해당 번호와 같다면 간식을 배부하고 리스트에서 빼는 것!
5. 둘 다 같지 않다면 간식줄에 있는 사람을 아래 빈 공간에 보낸다.
6. 이때 빈 공간에 사람이 있을 경우 해당 사람의 번호가 새로 들어오는 사람의 번호보다 커야 한다. 클 경우 “Sad”를 출력하고 종료한다. (번호가 작으면 번호표 순서대로 배부할 수 없기 때문)
7. 간식줄에서 배부가 끝나면 빈 공간을 본다. 빈 공간에 사람이 있을 경우 뒤부터 차례대로 현재 받아야 하는 사람의 번호와 같은지 비교한다.
8. 한 번이라도 맞지 않을 경우 번호표 순서대로 배부할 수 없는 경우로 “Sad”를 출력하고 종료한다.
9. 빈 공간에서도 배부가 끝나면 번호표 순서대로 간식 배부에 성공한 것으로 “Nice”를 출력한다.

---

☝🏻 주의 예제

5
1 3 2 4 5
>> "Nice"

---