[Baekjoon]백준 12789 도키도키 간식드리미(실버 3) - Python

문제설명 1

문제설명 2

문제를 살펴보면 순서가 뒤죽박죽 섞인 줄에서 순서대로 간식을 받아갈 수 있는지 확인하는 코드를 작성해야 한다

그림을 보면 쉽게 이해가 가능한데, 만약 다른 순서인 사람이 존재한다면 다른 하나의 줄에

스택처럼 순서대로 기다리게 한 뒤 적절한 순서가 되면 받아갈 수 있도록 짜여져있다

 

이 문제를 풀면서 최근에 풀었던 문제들 중에선 가장 고민을 많이 했던것 같다

입력받은 현재 줄 상태를 저장하는 리스트, 순서가 아닌 사람들을 순서대로 저장할 리스트 외에도 

나가는 사람들이 적절한 순서대로 나가는지 확인할 리스트의 필요성에 대해 고민을 하였다

시뮬레이션을 해보니 굳이 그럴 필요는 없긴하지만 그렇게

구현하기 위해선 현재 순서에 대해 저장된 변수가 존재해야한다 무한정 for문과 while문으로 확인할 수 없기 때문이다

 

for문을 통해 입력받은 리스트의 순서대로 확인을 하되,

현재 순서와 동일하다면 굳이 다른 동작 없이 현재 순서만 더해주면 된다

만약 그게 아니라면 다른 줄(다른 스택)에 append()를 통해 저장해주어야한다

 

지금의 코드(while 부분)를 작성하기 위한 알고리즘을 짜는데 가장 오랜 시간이 걸렸는데

stack의 길이가 0이 아니면서 stack의 가장 위, 즉 가장 마지막 요소가 현재 순서와 동일하다면 

stack에서 pop을 해주면서 현재 순서를 더해주어야한다

이 과정이 위의 그림 중 문제설명2의 세번째 그림에 해당한다

스택에 존재하는 숫자들이 현재 순서와 일치하다면 그만큼의 수를 스택에서 꺼내와야한다

 

마지막에는 stack 리스트에 요소가 존재한다면

순서대로 정렬에 실패한 것이므로 Sad를 요소가 존재하지 않다면 Nice를 출력하면 된다

앞으로도 많은 공부가 필요할 듯하다...

n = int(input())
line = list(map(int, input().split()))
stack = []

turn = 1
for student in line:
    if student == turn:
        turn += 1
    else:
        stack.append(student)
    while len(stack) != 0 and stack[-1] == turn:
        stack.pop()
        turn += 1
        
if len(stack) == 0:
    print('Nice')
else:
    print('Sad')