백준 12789번- '도키도키 간식드리미' (PYTHON 풀이)

문제:

 

해당 문제는 그림을 같이 제공해주어서 이해하는 것은 어렵지 않았다. 하지만 어떨 때 Sad가 되는지에 대한 이해는 필요하다고 생각해서 여러 경우의 수를 생각해보았다.

 

우선 해당 문제에서는 한줄씩으로만 들어갈 수 있는 공간이 있는데 거기에 줄 서있는 순서대로 한명씩 차곡차곡 옮길 수 있고 빠져나올 땐 반드시 최근에 들어간 순서대로 빼낼 수 있다. 최근 들어간 순서하면 떠오르는 자료구조가 있을 것이다. 바로 스택의 개념이다.

이 문제는 스택의 개념을 생각하면서 풀어야하는 문제이다. 스택을 생각해보면 앞서 말한 것처럼 마지막에 들어간 수부터 빼낼 수가 있다. 그러니까 줄 서 있는대로 스택에 옮겨놓은 다음 1을 만나면 1은 반드시 삭제해주고, 바로 옆에 2가 있지 않는 이상은 우선적으로 스택에 옮겨놓는다. 그 후에 끝에서부터 빼야하니까 순서대로 빼다가 순서에 맞지 않으면 Sad를 출력해야 한다.

 

예를 들어,

 

5
4 5 3 2 1

 

이런식으로 입력을 받는다고 치면, (4,5,3,2) 순으로 스택에 들어가게 될 것이고 1을 만나면 1은 자동으로 빼낸다. 그 후 끝에서부터 2,3 을 빼낸 다음 5를 만나면 이는 순서에 맞지 않으니까 Sad를 출력하게 될 것이다. 이러한 경우의 수를 생각하면서 문제를 풀면 쉽게 풀 수 있다.

 

풀이:

N = int(input())
li = list(map(int,input().split()))
stack = []
num = 1

for i in li:
    stack.append(i)
    while stack and stack[-1] == num:
        stack.pop()
        num += 1

if not stack:
    print('Nice')
else:
    print('Sad')

풀이는 다음과 같다. 크게 어려운 부분은 없는 것 같은데, 개인적으로 num을 설정해주는 게 중요하다고 생각한다.

입력받은 수를 하나씩 stack에 넣어주는데 최초에 찾아야 하는 수는 1이니까 초기에 num을 1로 설정해주고, 스택 조건에 맞게 -1 자리부터 천천히 돌면서 1인 순간을 찾는다. 그 후 찾게 되면 해당 수를 삭제하고, num을 증가해서 그 다음 수인 2를 찾도록 코드를 짜주었다.

마지막으로 스택이 비어있으면 알맞게 pop을 한거니까 Nice를 그렇지 않으면, Sad를 출력하게 해줌으로써 해당 문제를 풀 수 있다!