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

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

요구사항

• 시간 제한 1초
• 메모리 제한 128MB 

결론: 학생 수가 1,000이하 이므로 크게 신경 쓰지 않아도 됨

설계 1:

• current = 1 기다리는 번호 초기화
• 예제 입력 1 의 [5 4 1 3 2] 를 기다리는 번호라고 하자.
• for person in 기다리는 번호
  • person  ==  current일 경우 current += 1
  • 그 외는 stack 에 넣어주자.
• 스택이 있을 경우 while문을 돌려주자. 

# 입력 받기
n = int(input()
waiting_line = list(map(int, input().split()))

stack = []  # 보조 스택
current = 1  # 기다리는 번호

for person in waiting_line:
    if person == current:  
        current += 1  # 바로 간식 받기
    else:
        stack.append(person)  # 보조 스택에 넣기

# 보조 스택에서 처리
while stack:
    if stack[-1] == current:
        stack.pop()
        current += 1
    else:
        print("Sad")
        exit()

print("Nice")

위 구현의 문제점

• waiting_line을 모두 순회한 후에야 stack을 처리하고 있음.
• waiting_line을 순회하면서도 stack 에 있는 값이 바로 꺼낼 수 있는 지 즉시 확인해야함.

최종 구ㅎ

n = int(input()
waiting_line = map(int, input().split())

stack = []
current = 1

for person in waiting_line:
	while stack and stack[-1] == current:
    	stack.pop()
        current += 1
    if person == current:
    	current += 1
    else:
    	stack.append(person)
        
while stack and stack[-1] == current:
	stack.pop()
    current += 1

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