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]을 얻을 수 있다.
www.acmicpc.net
문제
코드
import sys
input=sys.stdin.readline
n = int(input())
p = [] # 입력 받은 수열
q = [] # 스택
s = [] # '+' or '-'
ans = [] # p와 일치 유무 확인
r = 1
for _ in range(n):
num = int(input())
p.append(num)
for i in range(len(p)):
while(True):
if r > p[i]: break
q.append(r)
s.append('+')
r += 1
# r > p[i]
if len(q) != 0:
ans.append(q.pop())
s.append('-')
if ans == p:
for k in s:
print(k)
else:
print('NO')
코드 풀이
입력 받는 수열( = 리스트 변수 p) 와 일치하는 수열( = 리스트 ans)가 나오면 수열 만들기 가능한 경우로 보고,
일치하지 않는다면, 'NO'를 출력하게끔 한다.
1부터 n까지의 범위의 자연수에 대해
스택 q에 넣을 수를 r로 설정한다.
스택에 push 연산인 append() 매써드 사용시 연산자로 이뤄진 리스트 s에 '+'을 더하고
이 연산은 while문을 통해 반복적으로 수행한다.
pop 연산을 할 경우 '-'을 리스트 s에 더한다.
이 연산은 while문을 탈출한 뒤 수행한다.
입력 받는 수열( = 리스트 변수 p)의 원소보다 큰 수를 스택 q에 넣는 것이 불가능하다.
이 때 while문을 탈출한다.
위 과정을 입력 받은 리스트 p에 대해 for문으로 반복한다.
조건문을 활용해
비교 대상이될 리스트 ans 가 리스트 p와 일치하면
True로 보고 연산자들을 출력한다.
불일치하면, 'NO'를 출력한다.
