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

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

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

# stack문제이다.

 

# 처음에 모든 인원들을 모두 stack에 넣고 풀어봤는데, 중간중간 필요할때 stack에 넣고 

   바로 빼는 상황이 필요해서 다시 풀었다.

 

1. idx가 N이 될때까지 반복문을 돌며 만약 stack안에 원소가 존재하고 stack[-1]이

   end(간식 받아야 할 사람)이면 end를 1증가 시켜주고 stack.pop()을 해준다.

   stack[-1]이 end가 아니면 student[idx]를 stack에 넣고 idx를 1증가 시켜준다.

 (ex: student가 [5, 4, 3, 2, 1, 10, 9, 8, 7, 6]이라면, while문을 다 돌았을때 end는 6이 되고

       stack은 [10, 9, 8, 7, 6]이 된다.)

 

2. student배열을 다 돌고 나서 stack에 원소가 남아있으면, 1번과정을 반복한다.

    그 과정에서 stack.pop()이 end가 아니면 더 이상 방법이 없으므로 "Sad"를 출력한다.

    모든 과정이 끝난 뒤 모든 사람들에게 간식을 다 나눠줬으면 end가 N+1일 것이므로 "Nice"를 출력한다.

 

from collections import deque
N = int(input())
student = list(map(int,input().split()))
stack = []
idx = 0
end = 1
while idx < N:
	if stack and stack[-1] == end:
		end += 1
		stack.pop()
	else:
		stack.append(student[idx])
		idx += 1

if stack:
	while stack:
		if stack.pop() == end:
			end += 1
		else:
			print("Sad")
			break

if end == N+1:
	print("Nice")

(solved.ac 티어: 실버 3)

 

# 복잡하고 어려운 자료구조나 알고리즘(위상정렬, 다익스트라, 플로이드와샬 등)을 사용하여 푸는

  문제들보다 이렇게 기본적인 자료구조를 응용해서 푸는 문제들이 티어는 더 낮은데,

  실제론 더 어려운 것 같다...