[BOJ 12789] 도키도키 간식드리미

문제 요약

문제 요약

한 명씩만 설 수 있는 공간 (스택)을 활용하여 순서가 뒤죽박죽인 대기열을 순서대로 간식 받는 곳에 들여보낼 수 있을까?
단, 대기열에서 스택으로 갈 수 있지만 반대는 불가능하다.
입력
첫째 줄 : 학생 수
둘째 줄 : 대기열의 뒤죽박죽인 순서
출력
순서를 원래대로 바꿀 수 있다면 Nice
아니라면 Sad

풀이

스택을 구현한 뒤 순서대로 넣는 시뮬레이션을 돌린 뒤 가능, 불가능을 판별한다.

어떤 식으로 순서대로 넣을 수 있을까?

대기열에서 순서대로 조사하면 된다.

1. 대기열 앞사람이 순서에 맞다면 간식 받는 곳에 들여보낸다.
2. 아니라면 스택의 top이 순서에 맞다면 들여보낸다.
3. 스택의 top도 순서가 아니라면 대기열 앞사람을 스택에 넣은 뒤 다음 사람을 조사한다.

위 1,2,3을 반복하면 된다.

그럼 불가능 하다는 것을 어떻게 알까?

위 1~3 과정을 진행할 때

1. 간식 받는 곳에 들어갈 순번
2. 현재 조사중인 대기열 순번

이 2가지의 index를 사용한다.

조사가 끝나는 원인 (1~3번을 돌리는 while문이 끝나는 원인)은
1. 간식 받는 줄에 모두 정렬 했을 때 (while 조건부 종료)
-> 1번 index가 사람 수보다 많아질 때
2. 조사하는 와중에 불가능한 것을 알았을 때 (break)
-> 2번 index가 마지막인데 top에서도 간식 받는 곳에 넣을 순번이 아닐 때

그럼 출력을 어떤 식으로 처리해야 할까?

가능, 불가능 모두 while문을 빠져나온다.
이 때 1번 index와 2번 index가 똑같은지 비교해서 가능과 불가능을 알아낼 수 있다.
결과 코드에선
1번 index : '간식 받는 곳에 들어갈 순번'이므로 1~N
2번 index : '조사중인 대기열 순번'에서 대기열이 배열이므로 0~N-1으로 두었다.
이 기준에 따르면 마지막에 1번 == 2번+1이 만족하면 Nice, 불만족할 시 Sad를 출력하면 된다.

신경써야 할 부분

역시 1000번 입력도 파이썬에선 오래 걸리므로 sys.stdin.readline을 사용한다.
논리 구조가 약간 복잡하므로 잘 생각하고 코드를 짜야한다.

결과 코드

import sys
input = sys.stdin.readline

class stack:
    def __init__(self):
        self.top = []
    def put(self, n):
        self.top.append(n)
    def pop(self):
        if not self.isEmpty():
            return self.top.pop()
        else:
            return -1
    def length(self):
        return len(self.top)
    def isEmpty(self):
        if self.length() == 0:
            return 1
        else:
            return 0
    def isTop(self):
        if not self.isEmpty():
            return self.top[self.length()-1]
        else:
            return -1

s = stack()
N = int(input())
waiting = list(map(int, input().split()))
next = 1; idx = 0
while next <= N:
	# 대기열 조사가 끝나지 않았고, 대기열 맨 앞 순번이 간식 받는 곳에 보낼 수 있다면
    if idx < N and waiting[idx] == next:
        next += 1; idx += 1
    else:
    	# 스택의 top이 간식 받는 곳에 보낼 수 있다면
        if s.isTop() == next:
            s.pop()
            next += 1
        # 없다면
        else:
        	# 조사가 안 끝났다면 대기열 맨 앞을 스택에 넣음
            if idx < N:
                s.put(waiting[idx])
                idx += 1
            # 조사가 끝났는데 스택 top에도 간식 순번이 없다면 break
            else:
                break

if next == idx+1:
    print('Nice')
else:
    print('Sad')