[백준/Python] 1874번: 스택 수열

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

문제

풀이

input = __import__('sys').stdin.readline
n = int(input())
x = 1
arr = []
out = []
flag = True

for _ in range(n):
    a = int(input())
    while 1:
        if arr and a<arr[-1]:
            flag = False
            break
        elif arr and a == arr[-1]:
            arr.pop()
            out.append("-")
            break
        else:
            arr.append(x)
            out.append("+")
            x+=1
    if not flag:
        print("NO")
        break
if flag:
    print("\n".join(out))  #이렇게 안 하고 매번 출력 하면 출력초과 생김.

스택에 1~n의 수를 차례대로 push하면서 중간중간 원하는 수를 pop하여 수열을 만드는 문제

-> arr을 stack으로 사용

1. n이 커질수록 입력 시행횟수가 증가하기에 표준입력으로 받을 수 있게 함.

2. 1~n까지 순서대로 push해야하기에 따로 x라는 변수를 만들어 1씩 증가하며 스택에 추가되도록 함.

3. if arr : 로 스택이 비어있는지 확인

4. 스택이 비어있으면 push

5. 비어있지 않을 때 스택의 Last In(arr[-1])과 수열의 다음 값인 a와 다르다면 push / 같다면 pop

6. 만약 스택의 Last In보다 수열의 다음 값이 작다면 pop할 경우 수열의 순서대로 원소를 가져올 수 없기에

    flag를 False로 초기화 후 모든 loop를 break