2022.02.25 [백준] (python 파이썬) 스택 수열

 

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

1874번: 스택 수열

---

풀이

이 문제는 1~n까지 배열에 넣으면서 최근에 들어간 배열의 값과 수열의 값을 비교해야한다.

그래서 stack을 이용했다.

1. arr에 주어진 수열을 넣는다.

2. while문을 시작하기 전에 1을 stack에 넣는다.( 이유는 만약 수열의 첫번째 숫자가 1이라도 일단 스택에 넣었다가 빼야하기 때문에 1을 넣었음)

3. while문을 돌려 수열의 첫 인덱스 값을 a에 넣고 만약 stack에 데이터가 있고 stack에 최근에 들어갔던 숫자(마지막 인덱스 값)가 a와 같으면 스택과 수열의 해당 값을 모두 pop으로 빼준다.

4. 만약 위의 조건이 아니면 x를 증가시킨 다음 x를 stack에 넣어준다. 

5. 만약 while문이 끝나기 전에 arr이 비었으면 수열을 모두 만들 수 있는 것이기 때문에 while문을 빠져나온다.

6. while문이 끝났을 때, arr에 데이터가 있으면 해당 수열은 만들어 지지 않기 때문에 NO를 출력한다.

7. 위의 조건이 아니면 정답을 담은 배열을 출력해준다. 여기서 +,-를 바로 출력하지 않고 배열에 담은 다음 출력한 이유는 만약 수열이 만들어 지지않으면 +,-가 출력되다가 NO가 출력되기 때문임.

import sys
input=sys.stdin.readline
 
n=int(input())
arr=[]
for _ in range(n):
    arr.append(int(input()))
stack=[]
x = 1
ans=[]
stack.append(x)
ans.append('+')
while x<=n:
    a=arr[0]
    if stack and a==stack[-1]:
        stack.pop()
        arr.pop(0)
        ans.append('-')
    else:
        x += 1
        stack.append(x)
        ans.append('+')
    if not arr:
        break
if arr:
    print('NO')
else:
    print('\n'.join(i for i in ans))