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

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

간단한 스택 문제이다. 문제의 핵심은 '어떻게 순서에 맞게 줄을 정리하냐'이다. 이때, 학생들의 번호표를 list를 직접 다룰지 stack에 쌓을지 고민할 수 있는데,  문제에서도 설명했다시피 임의로 설 공간을 제공하여 스택을 사용해야함을 간접적으로 알려준다. 시간 복잡도 또한 list 순회와 마찬기지로 O(n)밖에 되지 않는다. 그 이후에 순서와 관련된 문제는 별도의 변수 turn을 사용하여 stack의 마지막 요소와 일치할 때마다 stack의 마지막 요소를 pop하고 turn += 1을  사용하면 해결된다.

 

코드

import sys
N = int(sys.stdin.readline().strip())
line = list(map(int, sys.stdin.readline().split(' ', N - 1)))
turn = 1
stack = []
for i in range(len(line)):
    stack.append(line[i])
    while stack and turn == stack[-1]:
        stack.pop()
        turn += 1
if stack:
    print('Sad')
else:
    print('Nice')