25556 포스택 - 골드5

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

1. 문제

포닉스는 길이가 N인 순열 A와 네 개의 비어 있는 스택을 가지고 있다.

길이가 N인 순열이란, 1 이상 N 이하의 서로 다른 정수 N개가 임의로 나열된 수열을 말한다.

스택이란 자료구조의 한 종류로 가장 나중에 삽입한 자료가 가장 먼저 나오는 후입선출 (Last In First Out, LIFO)의 특성을 가지고 있다. 포닉스는 PPC를 맞아 더러워진 순열을 청소하려 한다.

순열을 청소하는 것은 다음과 같은 과정을 통해 순열을 오름차순으로 정렬하는 것을 뜻한다. 즉 순열을 1, 2, 3, N으로 만들어야 한다.

1. 순열 A의 원소들을 앞 원소부터 순서대로 네 개의 스택 중 하나에 삽입한다.
2. 순열 A의 모든 원소를 스택에 삽입했다면, 네 개 중 원하는 스택에서 수를 꺼내는 것을 반복하여 네 개의 스택에서 모든 수를 꺼낸다.
3. 꺼낸 수들을 꺼낸 순서대로 오른쪽에서 왼쪽으로 나열한다. 즉, 가장 처음에 꺼낸 수가 맨 뒤, 가장 나중에 꺼낸 수가 맨 앞에 위치하게 된다.

포닉스가 주어진 순열을 청소할 수 있는지 판별해 보자.

입력 첫째 줄에 순열의 길이 N이 주어진다. (1 ≤ N ≤ 100,000)

둘째 줄에 순열 A의 원소 A_i가 공백으로 구분되어 주어진다. 모든 A_i는 1 이상 N 이하의 서로 다른 정수임이 보장된다.

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

예제 1

10
4 3 6 7 8 9 10 2 1 5 => YES

예제 2

5
5 4 3 2 1 => NO

2. 정답 소스코드

import sys

n = int(sys.stdin.readline().rstrip())
a = list(map(int, sys.stdin.readline().split()))

isTrue = True
stack1 = []
stack2 = []
stack3 = []
stack4 = []

for ele in a :
    if not stack1 :
        stack1.append(ele)
    elif stack1[-1] < ele :
        stack1.append(ele) 
    elif not stack2 :
        stack2.append(ele)
    elif stack2[-1] < ele :
        stack2.append(ele)
    elif not stack3 :
        stack3.append(ele)
    elif stack3[-1] < ele :
        stack3.append(ele)
    elif not stack4 :
        stack4.append(ele)
    elif stack4[-1] < ele :
        stack4.append(ele)  
    else :
        isTrue = False
        break

if not isTrue :
    print("NO") 

else :
    while n > 0 :
        if stack1 and stack1[-1] == n :
            stack1.pop()
            n -= 1
        elif stack2 and stack2[-1] == n :
            stack2.pop()
            n -= 1
        elif stack3 and stack3[-1] == n :
            stack3.pop()
            n -= 1
        elif stack4 and stack4[-1] == n :
            stack4.pop()
            n -= 1
        else :
            isTrue = False
            break
    
    if not isTrue :
        print("NO")
    else :
        print("YES") 

3. 풀이 방법

• 시간복잡도 : O(n)
• 4개의 stack에서 값을 꺼내어 정리했을 때, 1 ~ n까지 오름차순이어야 한다.
  • 예를 들어, n = 5 라고 한다면, 정리 순서는 1,2,3,4,5가 되어야 한다.
• 따라서, stack에 값을 넣을 시, 추후 큰 값부터 pop이 되어야 하므로,작은 숫자가 먼저 들어가고 큰 숫자가 stack의 top에 있는 모양이 되어야 한다.