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

문제

시험기간에 간식을 번호 순서대로 나눠주려고한다. 간식을 받기위해 사람들이 번호에 상관없이 무작위인 일렬로 서있고 차례대로 간식을 받으려고 한다. 이때 자신의 차례가 아닐 때는 한 명이 들어갈 수 있는 공간으로 빠지게된다.

이렇게 마지막 번호까지 모두 간식을 순서대로 받을 수 있는지 구해보자.

 

입력

입력의 첫째 줄에는 현재 승환이의 앞에 서 있는 학생들의 수 N(1 ≤ N ≤ 1,000,자연수)이 주어진다.

다음 줄에는 승환이 앞에 서있는 모든 학생들의 번호표(1,2,...,N) 순서가 앞에서부터 뒤 순서로 주어진다.

 

출력

간식을 받을 수 있으면 "Nice"(따옴표는 제외)를 출력하고 그렇지 않다면 "Sad"(따옴표는 제외)를 출력한다.

---

접근

스택과 큐를 활용하였다. 기존에 줄이 서있는 사람들을 큐에 넣고 옆의 통로를 스택으로 구현하였다. 

먼저 큐에 맨 앞에 있는 사람의 번호를 확인하고 순서가 아닐 때는 스택을 확인한다.

스택에도 순서가 없을 때는 큐에서 맨 앞에있는 사람을 스택에 넣는다.

하지만 이때 큐에 더 이상 사람이 존재하지 않을 때는 모두가 순서대로 간식을 받을 수 없는 상황이된다.

 

구현

- 번호가 N이 된 것은 간식을 모두 받았다는 것이기 때문에 while문을 종료한다.

- 아직 줄을 서있는 학생이 존재하고 맨 앞의 학생이 받을 차례라면 간식을 준다.

- 그렇지 않다면 옆의 통로인 스택을 확인하여 간식을 받을 차례인 번호가 있는지 확인하고 있다면 간식을 준다.

- 위 두개의 조건이 아닐 시에 줄 서있는 학생이 없다면 더 이상 순서대로 간식을 줄 수 없기 때문에 종료하고

- 아직 줄 서있는 학생이 있다면 맨 앞에 있는 학생을 옆의 통로로 옮긴다.

while number <= N:
    if students and number == students[0]:
        number += 1
        students.popleft()
    elif stack and number == stack[-1]:
        number += 1
        stack.pop()
    else:
        if not students:
            break
        else:
            cur = students.popleft()
            stack.append(cur)

---

전체 코드

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

N = int(input())
students = deque(map(int, input().split()))

number = 1
stack = []

while number <= N:
    if students and number == students[0]:
        number += 1
        students.popleft()
    elif stack and number == stack[-1]:
        number += 1
        stack.pop()
    else:
        if not students:
            break
        else:
            cur = students.popleft()
            stack.append(cur)

if number > N:
    print('Nice')
else:
    print('Sad')