[Stack] 주차 관리인

스택: LIFO(Last-In, FIrst-Out)

스택 정렬: 스택의 내용을 빈 스택 하나를 이용해서 정렬하는 알고리즘

강의교재에서 본 주차장의 주차 관리인에게 주차 주문이 도착했다.
이 주차 주문에 따르면, 1번부터 N번까지의 차량이 오른편에서 차례대로 도착하고 있을 때,
왼편의 주차 공간에 주차 주문의 차량 번호 순서에 따라 주차를 해야 한다.
이 주차장은 스택처럼 생긴 하단부의 임시 공간을 이용해서 주차 순서를 조정할 수밖에 없음을 알고 있을 것이다.
또한, 한 번 주차장 안으로 들어온 차량은 거꾸로 빼낼 수도 없다.
그렇기 때문에, 때로는 주차 주문에 적힌 주차 순서가 주차하기가 불가능한 순서일 수도 있다.
예를 들어, 주차 계획의 차량 번호 순서가 다음과 같다고 하자.
5 4 1 2 3
차량의 도착 순서가 1 2 3 4 5 이므로 5번 차량을 제일 안쪽으로 주차하려면 스택에 1 2 3 4를 차례대로 push해야 한다.
따라서, 5번 다음에 4번을 주차할 수는 있지만, 4번 다음에 와야 할 1번 차량은 스택의 아래쪽에 있으므로 4번 뒤에 주차할 수 없다.
M개의 주차 주문이 주어졌을 때, 이 주차 주문이 가능하면 "yes"를 불가능하면 "no"를 출력하시오.

input
첫째 줄에 차량의 대수 N과 주문의 개수 M이 주어진다.
둘째 줄부터 M개의 줄에 주차 주문이 한 줄에 하나씩 주어진다.
4 24
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1

output
첫째 줄부터 M개의 줄에 각 주차 주문이 주차가능하면 "yes"를, 불가능한며 "no"를 출력한다.
yes
yes
yes
yes
no
yes
yes
yes
yes
yes
no
yes
no
no
yes
yes
no
yes
no
no
no
no
no
yes

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
carorder = [list(map(int, input().split())) for _ in range(m)] # 주차해야 하는 순서

def sol(carorder):
    stack = [] # 임시 stack
    mycar = [i+1 for i in range(n)] # 1~n까지의 차량
    parking=[] # 주차 완료 후 주차 순서
    index=0
    while len(mycar): # n개의 차량을 꺼내서 주차 수행
        current = mycar.pop(0) # 제일 앞에꺼 pop
        stack.append(current) # 일단 임시 stack에 push
        while len(stack) and stack[-1]==carorder[index]:
            parking.append(stack.pop())
            index+=1
    while len(stack): #임시 stack을 비워서 parking에 다 넣음
        parking.append(stack.pop())
    return parking # 주차 완료 후 parking을 return

def answer(a, b): # 원하는 주차 순서(carorder[i])와 parking이 동일하면 yes
    if a==b:
        return 'yes'
    else:
        return 'no'

for i in range(m):
    print(answer(sol(carorder[i]), carorder[i]))

1. mycar의 제일 앞의 값을 꺼내서 일단 stack에 넣음

2. stack의 제일 위의 값과 carorder[index]의 값과 비교

3-1. 일치한다면? stack pop후 parking에 주차 후 index+=1

3-2. 일치하지 않는다면 1,2를 수행

4. 모든 mycar를 수행 후 stack에 남는게 있으면 모두 parking에 주차

5. parking의 결과와 carorder가 일치한다면 yes출력