1874번 스택 수열

문제링크 : www.acmicpc.net/problem/1874

1874번: 스택 수열

---

---

<문제 풀이 근거>

  ex ) 주어진 수열 : 2 3 4 6 1 5 8 7

        위의 주어진 수열의 push pop을 진행하면 아래와 같다

        [1]         push

        [2,1]       push

        [1]         2 pop

        [3,1]       push

        [1]         3 pop

        [4,1]       push

        [1]         4 pop

        [5,1]       push

        [6,5,1]     push

        [5,1]       6 pop

                               = 1 pop 불가능

         

이는 주어진 수열에서 i번째 값보다 i+1번째 값이 작을때,

i번째 값과 i+1번째 값 사이의 값들이 이미 이전의 pop되었어야 함을 의미한다.

                                                                                    = 수열에서 앞에 등장했어야 함

 

 

<알고리즘>

  1) 우선 원하는 수열을 배열에 input

  2) 원하는 수열을 차례대로 보면서 i번째 수보다 i+1번째 수가 작을 때, 앞서 i번째 수와 i+1번째 사이의 수들이 먼저 등장했는지 확인해서 No를 출력할지 push pop 과정을 거칠지 판단

   3) now를 증가시켜가면서 push하고 원하는 수열값과 stack의 top이 일치하면 pop하기

 

 

 

( 메모리 : 33412KB    시간 : 2864ms )

stack = [0]
def push(a):
    print("+")
    stack.insert(0,a)
def pop():
    print("-")
    del stack[0]
def top():
    return stack[0]

import sys
N = int(sys.stdin.readline())

want = []
for _ in range(N):
    want.append(int(sys.stdin.readline()))

flag =True
check = [False for _ in range(len(want)+1)]
for i in range(0, len(want)-1):
    if(flag == True):
        check[want[i]] = True
        check[want[i+1]] = True
        if(want[i]>want[i+1]):
            for j in range(want[i+1],want[i]):
                if(check[j]==False):
                    flag = False


if(flag == False):
    print("NO")
else:
    now = 0
    while(len(want)!=0):
        now+=1
        push(now)
        while(True):
            if((len(want)!=0)and (top()==want[0])):
                pop()
                del want[0]
            else:
                break