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

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

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

문제 풀이

학생들이 처음 서 있는 줄은 먼저 들어온 사람이 먼저 나가는 FIFO 구조이므로 queue를 이용하면 된다.(편의상 deque를 이용하여 구현하였다.)

 

그리고 학생들이 순서대로 입장하기 위해 잠시 머무는 줄은 LIFO 구조이므로 stack을 이용하면 된다.

이제 준비는 끝났다. 문제에서 원하는대로, queue에서 또는 stack에서 순서(order)에 맞는 사람이 res 리스트에 입장하면 된다. 입장할 사람이 없으면 큐에 있는 사람이 스택에 우선 머무는 것으로 하고, 만약 입장할 사람도 없고, 큐에서 스택에 머물 사람도 없는 경우라면 순서대로 입장할 수 없는 경우이므로 반복문을 탈출한다.

 

정답을 ans 변수에 만들어두고, res 리스트와 ans 리스트를 비교하여 일치한다면(순서대로 입장한 경우라면) "Nice"를, 아니라면 "Sad"를 출력하게 한다.

 

제출 코드

from collections import deque
import sys
input = sys.stdin.readline

N = int(input())
queue = deque(map(int, input().split()))
res = list()
stack = list()
order = 1

while True:
    if order > N: break
    elif len(stack) > 0 and stack[-1] == order:
        tmp = stack.pop()
        res.append(tmp)
        order += 1
    elif len(queue) > 0 and queue[0] == order:
        this = queue.popleft()
        res.append(this)
        order += 1
    elif len(queue) > 0:
        this = queue.popleft()
        stack.append(this)
    else: break
ans = [i for i in range(1, N+1)]
if res == ans:
    print("Nice")
else:
    print("Sad")

느낀 점

자료구조에 대한 문제였다. 본격적으로 문제에서 자료구조를 적극적으로 적용하게끔 하는 문제를 처음 만나봤다. 문제에서 요구하는 상황에 따라 적합한 자료구조를 적용하는 것이 재밌게 느껴졌다.