[백준/python] 12789번: 도키도키 간식드리미

문제

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

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

---

문제 요약

학생들 수 N과 그 학생들의 번호표 순서를 입력받고 무사히 간식을 받을 수 있다면 'Nice' 아니면 'Sad'를 출력한다.

 

사람들은 1열로 줄을 서있고, 맨 앞 사람만 이동이 가능하다.

번호표 순서대로만 통과할 수 있는 라인이 있다. 

라인과 대기열의 맨 앞사람 사이에는 1열이 들어갈 수 있는 공간이 있다.

 

 + 위 링크 사진 참고

---

코드

import sys
input = __import__('sys').stdin.readline

def main():
    N = int(input())
    now = 0
    st = []
    arr = list(map(int, input().rstrip().split()))

    while True:
        if arr and now + 1 == arr[0]:
            now = arr.pop(0)
        elif st and st[-1] == now + 1:
            now = st.pop()
        else:
            if not arr:
                print('Sad')
                break
            else:
                st.append(arr.pop(0))

        if now == N:
            print('Nice')
            break

if __name__ == "__main__":
    main()

---

코드 설명

1. 승환이 앞에 서 있는 학생들의 수 N과 번호표를 가진 학생들의 대기 줄(arr)을 리스트로 입력 받는다.

 

2. 변수 now는 현재까지 간식을 받은 번호이다.

(now + 1은 다음 간식을 받을 번호)

 

3. 스택 st는 라인과 대기열 맨 앞 사람 사이 1열이 들어갈 수 있는 사이 공간을 의미한다.

 

4. 무한 루프를 이용하여 무엇을 할 지 정한다.

 

4-1. 만약 대기 줄에 사람이 있고 다음 간식을 받을 번호가 맨 앞 줄에 있는 사람의 번호(arr[0])와 같다면, 맨 앞 줄에 있는 사람에게 간식을 주고(배열 arr에서 pop(0)), 현재까지 간식을 받은 번호를 그 사람의 번호로 저장한다.

=> 대기 줄 arr에서 맨 앞 사람이 간식 받는 곳(now)으로 이동한 경우

 

4-2. 만약 사이 공간에 사람이 있고, 나갈 수 있는 맨 앞 사람의 번호(st[-1])가 다음 간식을 받을 번호(now + 1)라면, st 맨 앞 줄에 있는 사람에게 간식을 주고 (스택 st에서 pop), now를 그 사람의 번호로 저장한다.

=> 사이 공간 st에서 맨 앞 사람이 간식 받는 곳(now)으로 이동한 경우

 

4-3. 대기 줄과 사이 공간 맨 앞에 있는 두 사람 모두 다음 간식을 받을 번호(now + 1)이 아닐 때,

 

4-3-1. 대기 줄에 사람이 있다면, 대기줄 맨 앞 사람이 일단 사이 공간으로 가서 기다린다.

(뒤에 더 빠른 번호가 있을 수 있으므로)

=> 대기줄 arr에서 사이공간 st로 이동한 경우

 

4-3-2. 대기 줄에 사람이 없다면, 승환이는 간식을 받을 수 없는 상황이므로 'Sad'를 출력하고 반복문을 종료한다.

 

4-4. 만약 간식을 받은 번호가 승환이 앞에 있는 사람들 수와 같다면, 승환이 앞 사람들이 모두 간식을 받았기 때문에 승환이는 간식을 받을 수 있는 상황이므로 'Nice'를 출력하고 반복문을 종료한다.