[Python] 파이썬 백준(1874) 스택 수열

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

1874번: 스택 수열

---

나의 풀이

1부터 n까지 수를 스택에 넣었다가 늘어놓음으로 하나의 수열을 만들 수 있음

이를 스택을 이용해 수열을 만들 수 있는지 없는지 있다면 push(+)와 pop(-)을 어떻게 수행해야하는지 출력함

문제가 좀 이해하기 힘든데 push랑 pop을 기준으로 이해하면 됨

8 4 3 6 8 7 5 2 1

+ + + + - - + + - + + - - - -

---

• len_max를 만들어 들어왔던 수 중 가장 큰 수를 저장하여 새로운 list 생성시 이전 다음부터 생성되도록 함
• 값이 증가함에 따라 answer에 +도 증가시키고 pop 할 때 -를 저장함
• pop한 수가 num하고 다르다면 수열이 되지 못하는 수열이며 no를 출력함

import sys
cnt = int(sys.stdin.readline())
len_max = 1
sequence = []
answer = []
for _ in range(cnt):
    num = int(sys.stdin.readline())
    sequence += [i for i in range(len_max,num+1)]
    answer += ['+' for _ in range(len_max,num+1)]
    if sequence.pop() != num:
        break
    answer += ['-']
    if len_max <= num:
        len_max = num+1
if sequence:
    print('NO')
else:
    print('\n'.join(answer))

---

다른 사람의 풀이

list의 슬라이스가 맞지 않으면 추가되지 않아 위처럼 코드를 작성하였는데 cnt<= num으로 while문을 돌려 cnt 만큼 추가시키고 cnt<=num가 아닐 때는 스택을 따라야하기 때문에 pop을 통해 일괄처리함

[i for i in range()] 이 과정에 시간이 오래 걸렸나봄

import sys
n = int(input())
cnt = 1
stack = []
ans = []
for i in range(n):
    num = int(sys.stdin.readline())
    while cnt<=num: #cnt 스택에 push
        stack.append(cnt)
        ans.append('+')
        cnt+=1
        #print(ans)
    if stack.pop()==num: #stack의
        ans.append('-')
        #print(ans)
    else:
        print("NO")
        break
else:
    print("\n".join(ans))