[스택] 접시 / python

문제

예제 입출력

💡 사고의 흐름

• input -> 입력받는 접시 순서
• 알파벳(len(input)) 만큼 스택에 넣으면서, stack[top]과 Input[idx]와 같은 값인지 비교!(top = -1, idx = 0)
• stack[top]==input[idx]인 경우, 스택에 있는 모든 문자를 pop
• 만약 이때, pop된 문자와 input이 같다면 -> 접시 꺼내는 것 가능!(push,pop 순서대로 출력)
• 다르다면, impossible 출력
  가장 중요한 것은, 알파벳 순서대로 스택에 쌓고 pop된 것이 input의 알파벳 순서와 동일할 때, 접시에 넣을 수 있다는 것

Code

import sys
input = list(sys.stdin.readline())
stack=[]
flag = True
idx=0
top=-1
result=[]
compare=[]

for i in range(len(input)):
  stack.append(chr(ord('a')+i))
  result.append('push')
  top+=1
  if stack[top]==input[idx]:
    while(top>-1):
      compare.append(stack.pop())
      top-=1
      idx+=1
      result.append('pop')
      if idx>=len(input):
        break

for i in range(len(input)):
  if len(compare)==len(input):
    if input[i]!=compare[i]:
      flag=False
  else:
    flag=False

if flag==True:
  for r in result:
    print(r)
else:
  print('impossible')