[백준/파이썬]1874번 스택수열

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

1874번: 스택 수열

문제

어려웠다.

 

처음엔 문제 밑에 있는

1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다.

 

이 힌트를 보고 그럼 그냥 반대로 하면 되는 거 아닌가?라는 생각을 가지고

[4, 3, 6, 8, 7, 5, 2, 1] 이 수열에서 

뒤에서 부터 -1 인덱스와 -2 인덱스를 비교해서 -2 인덱스가 더 크면 pop 해주고 이게 아니면 push해주는 식으로 풀려고 했다.

 

그렇게 되면

pop할때

ans.append("+")

push 할 때

ans.append("-")

(반대라서 헷갈리지만 stack 따위 쓰지 않고 그냥 내 생각대로 풀어서 요 모양이다.)

 

그럼

뒤에서부터 했으니까

처음 pop 된 5개를 모으면

a = [1, 2, 5, 7, 8]이 된다.

여기서 6을 만나게 되는데, 그럼 6이 더 작으니까 1, 2, 5, 7, 8중에 가장 끝에 있는 8을 다시 꺼내준다.

7이랑도 비교를 해보면 똑같이 7도 꺼내준다.

이때는

ans.append("+")

해주고

6을 a리스트에 넣을 땐 

ans.append("-")

 

대충.. 이런 식으로 풀어야겠다 싶었는데 복잡하기도 하고, 입력 값이 최대 100,100개다 보니 내가 생각한 알고리즘으로 풀게 되면 최악의 경우 O(n^2)의 시간 복잡도가 나오게 된다.

 

그래서 깔끔하게 생각을 접고 구글링을 했다ㅋ

 

정말 많은 블로그들을 보면서 이해를 해봤다.

이렇게 풀 생각을 하는 사람들이 있다는 게 신기했다.

 

정답

import sys

n = int(input())
stack = []
ans = []
c = 0
for i in range(1,n+1) :
    stack_num = int(sys.stdin.readline().rstrip())
    while c < stack_num :
        stack.append(c+1)
        ans.append("+")
        c += 1
    if stack.pop() == stack_num :
        ans.append("-")
    else :
        print("NO")
        sys.exit(0)

print('\n'.join(ans))

---

나름 쉽게 풀 줄 알았는데 시간을 엄청 잡아먹어 버렸다..