백준 #25556 포스택

코드

import sys
# sys.stdin = open("input.txt")
input = sys.stdin.readline

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

"""
무조건 stack 최상단 수보다 큰수를 삽입해야함
"""
check = True
for x in arr:
    for i in range(4):
        if not stack[i]:			# 스택이 비어있으면 삽입
            stack[i].append(x)
            break					# 나머지 스택에 대해선 볼 필요가 없으므로
        else:
            if stack[i][-1] < x:	# 오름차순으로 넣을 수 있는 경우에만
                stack[i].append(x)
                break
    else:
        check = False				# 숫자를 어느 스택에도 넣을 수 없으면
        break

if check:
    print("YES")
else:
    print("NO")

풀이

생각보다 간단했던 문제이다.

스택 4개를 만들어 주고 각각의 숫자에 대해서 스택 4개를 방문을 한다.

스택 맨 위의 숫자가 현재의 숫자보다 작을 경우에만 스택에 넣어준다.

즉, 각각의 스택에는 스택 바닥부터 순서대로 오름차순 정렬이 되어있는 상태이다.

만약 4개의 스택 어느 곳에도 들어가지 못한다면 불가능한 상황으로 판단한다.

끝!