백준 1874 파이썬 스택 수열

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

1874번: 스택 수열

 

문제를 처음에 맞닥뜨리고 무슨 말을 하는건지 이해하는 데까지 시간이 꽤 걸렸다. 결국 손으로 써보고 나서야 감을 잡았는데, 이해한 내용을 대략적으로 설명해보겠다.

 

  주어진 수열이 가진 원소들을 오름차순을 지켜서 스택에 push해야 한다. 이후 pop을 이용해 주어진 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 만든다. 실제 과정을 나열해보면,

 

1. stack = [ ],        cnt = 0, num = 4, res = [+]

2. stack = [1],       cnt = 1, num = 4, res = [+, +]

3. stack = [1,2],     cnt = 2, num = 4, res = [+, +, +]

4. stack = [1,2,3]    cnt = 3, num = 4, res = [+, +, +, +]

5. stack = [1,2,3,4]  s[-1] == num,       res = [+, +, +, +, -]       pop 4   

6. stack = [1,2,3]    s[-1] == num,       res = [+, +, +, +, -, -]    pop 3    

 

   이런 식으로 stack을 비울 때까지 반복하여 수열을 만들 수 있는지 확인하고, push와 pop을 연산 순서를 결과로 출력한다. 두번째 예제인 수열 [1, 2, 5, 3, 4]의 경우에는 [3]을 pop하는 과정에서 top에 위치한 [4] 때문에 주어진 수열을 얻어낼 수 없어서 "NO"라는 결과를 출력한다. 수열을 만들 수 없는 상황을 위해 True/False 변수를 넣어주었다.

 

n = int(input())
s = []
res = []
ans = True
cnt = 0

for i in range(n):
    num = int(input())
    while cnt < num:
        cnt += 1
        s.append(cnt)        
        res.append("+")
    if s[-1] == num:
        s.pop()
        res.append("-")
    else:
        ans = False
        break

if ans == False:
    print("NO")
else:
    for i in res:
        print(i)

 

그간 100문제 가량 풀어 노션에 기록을 해놓았었는데, 차차 블로그에도 옮길 예정이다.