[BOJ 25556 / Python] 포스택

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

25556번: 포스택

 

오랜만에 올리는 포스팅 ㅎㅎ

 

블로그 쉬지 않고 열심히 올려보자아~

 

위 문제는 직접 손으로 그려보면서 "되는 경우"를 찾는게 매우 쉽다.

 

규칙은 딱 2가지다.

 

1) 4개의 stack 중 한개라도 비어있지 않은 상황일때, 비어있지 않은 그 stack의 top보다 지금 넣으려는 숫자가 반드시 커야한다.

2) 만약 넣으려는 숫자가 작다면, 반드시 비어있는 stack에 넣어야한다. 

3) 만약 비어있는 stack이 존재하지 않는다면, 그 배열은 청소가 불가능하다.

 

# -*- coding: utf-8 -*-
import sys
input = sys.stdin.readline

def sol(nums):
    stack1 = []
    stack2 = []
    stack3 = []
    stack4 = []
    stacks = [stack1, stack2, stack3, stack4]


    for n in nums:
        check = True
        for i in stacks:
            if i and i[-1] < n : # stack이 비어있지 않고 해당 top보다 지금 넣으려는 값(n)이 더 크다면,
                i.append(n) # n을 추가함
                check=False
                break

            if not i : # 만약 해당 stack이 비어있으면
                i.append(n)
                check=False
                break
            
        if check:
            return False # 여기에 도달하면 위의 조건에도 성립되지 않으므로 종료시킴.
            
    return True


n = int(input())
arr = list(map(int, input().rstrip().split()))

if sol(nums=arr) :
    print("YES")
else :
    print("NO")