문제
문제 요약
사람들은 현재 1열로 줄을 서있고, 맨 앞의 사람만 이동이 가능하다. 인규는 번호표 순서대로만 통과할 수 있는 라인을 만들어 두었다. 이 라인과 대기열의 맨 앞 사람 사이에는 한 사람씩 1열이 들어갈 수 있는 공간이 있다. 현재 대기열의 사람들은 이 공간으로 올 수 있지만 반대는 불가능하다.
현재 간식 배부 공간을 그림으로 나타내면 다음과 같다.
위 예제는 다음 그림과 같이 움직였을 때 모두가 순서대로 간식을 받을 수 있다.
입력
입력의 첫째 줄에는 현재 승환이의 앞에 서 있는 학생들의 수 N(1 ≤ N ≤ 1,000,자연수)이 주어진다.
다음 줄에는 승환이 앞에 서있는 모든 학생들의 번호표(1, 2, ..., N) 순서가 앞에서부터 뒤 순서로 주어진다.
출력
승환이가 무사히 간식을 받을 수 있으면 "Nice(따옴표는 제외)"를 출력하고 그렇지 않다면 "Sad"(따옴표는 제외)를 출력한다.
Python 코드
풀이
학생들이 처음 서 있는 줄은 먼저 들어온 사람이 먼저 나가는 FIFO 구조이므로 queue를 이용한다.
(편의상 deque를 이용하여 구현)
그리고 학생들이 순서대로 입장하기 위해 잠시 머무르는 줄은 LIFO 구조이므로 stack을 이용하면 된다.
이제 queue에서 또는 stack에서 순서(order)에 맞는 사람이 res 리스트에 입장하면 된다. 입장할 사람이 없으면 큐에 있는 사람이 스택에 우선 머무는 것으로 한다. 만약 입장할 사람도 없고, 큐에서 스택에 머물 사람도 없는 경우라면 순서대로 입장할 수 없는 경우이므로 반복문을 탈출한다.
정답을 ans 변수에 만들어두고, res 리스트와 ans 리스트를 비교하여 일치한다면 "Nice"를, 아니라면 "Sad"를 출력한다.
