[Python/파이썬] 백준 12789번 도키도키 간식드리미

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

 

코드

n = int(input())
nums = list(map(int, input().split()))

stack = []
cnt = 1
for i in range(n):
    if cnt == nums[i]:  # 순서가 맞는 사람
        cnt += 1
    else:   # 순서 안 맞는 사람
        while stack:    # stack에서 나갈 수 있는 사람 나가기
            if stack[-1] == cnt:
                stack.pop()
                cnt += 1
            else:
                break
        stack.append(nums[i])

# stack에 남은 사람들 중 나올 수 있는 사람
while stack:
    if stack[-1] == cnt:
        stack.pop()
        cnt += 1
    else:
        break

if stack:
    print("Sad")
else:
    print("Nice")

 

반복문을 돌며 순서가 맞는 사람은 바로 보내고, 순서가 맞지 않는 사람은 stack으로 보낸다. 이때 stack의 top에 있는 사람부터 아래로 차례대로 조사하여 현재 호명된 번호인 cnt와 일치하는 사람은 모두 내보낸 뒤에 nums[i]를 넣어야 한다.

 

그리고 마지막에 stack에 남아있던 사람들도 한 번 다시 조사하여 번호대로 나갈 수 있는 사람은 모두 내보낸다.

 

이렇게 했는데도 stack에 남은 사람들이 있다면 그건 모든 사람이 순서대로 간식을 받을 수 없다는 것이다.