[Python] 백준 25556: 포스택

solved.ac 기준 Gold 5

문제

입력

출력

포닉스가 순열을 청소할 수 있으면 YES, 불가능하다면 NO를 출력한다.

예제 입력 1

10
4 3 6 7 8 9 10 2 1 5

예제 출력 1

YES

예제 입력 2

5
5 4 3 2 1

예제 출력 2

NO

 

정답 코드

N = int(input())
arr = list(map(int, input().split()))

stack = [[], [], [], []]
result = 'YES'

for i in range(N):
    num = arr[i]

    is_appended = False
    for j in range(4):
        if not stack[j] or stack[j][-1] < num:
            stack[j].append(num)
            is_appended = True
            break

    if not is_appended:
        result = 'NO'
        break

print(result)

 

 스택의 원리를 적절하게 사용할 수 있어야 한다. 순열을 앞에서 부터 탐색하면서, 탐색한 정수를 스택 중 한 곳에 push해야 하는데, 나중에 pop을 하면서 오름차순으로 만드려면 무조건 스택의 top에는 항상 앞서 들어온 정수들 보다 큰 정수가 들어가 있어야 한다. (오른쪽에서 왼쪽으로 배치하므로) 

 

 해당 규칙을 활용하여, 순회를 하면서 스택 중 어느 곳에도 넣을 수 없으면 그것은 청소가 불가능한 것이므로 바로 탈출해 NO를 출력한다. 만약 순회가 모두 완료되면 청소가 가능한 것이므로 YES를 출력한다.