[백준] 1874번: 스택 수열 python

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

1874번: 스택 수열

 

문제 정보

스택

실버3

1h20m

X

설계 방법

입력한 수를 만날 때 까지 오름차순으로 push

입력한 수를 만나면 while문 탈출. 즉 cnt = num일 때까지 while문을 돌아 스택을 쌓음

stack의 top이 입력한 숫자와 같다면 스택의 top을 꺼내 수열을 만들어 줌

stack의 top이 입력한 수가 아니라면 주어진 스택을 만들 수 없음

오름차순으로 스택이 입력되는데 top이 num보다 크면 num은 top보다 더 아래에 쌓여있기 때문

코드

n = int(input())
stack=[]
op = []
cnt = 1
temp = 0

for i in range(n):
  num = int(input())
  while cnt <= num:
    stack.append(cnt)
    op.append('+')
    cnt+=1
  if stack[-1] == num:
    stack.pop()
    op.append('-')
  else:
    print('NO')
    temp+=1
    break

if temp == 0:
  for i in op:
    print(i)

시간 복잡도

$O(n^2)$

어려웠던 점

문제를 이해하는 것 부터가 어려웠는데 이해하고나서도 어떤식으로 구현해야할지 감이 안잡혀서 고생했다

스택 자료구조를 이용하는 것을 알고 있었음에도 불구하고 1,2,3,4라는 숫자를 i+1로 stack에 넣어야한다고 생각하니 어려움이 있었는데 cnt로 쉽게 넣을 수 있구나 깨달았다

python list에서 제공해주는 [-1]이런 것들을 알기만 알고 문제에 적용하는 능력이 떨어지는 것 같다

참고 자료

https://pacific-ocean.tistory.com/231

https://hongcoding.tistory.com/39