[day6] 백준 1874번 스택 수열 (Python)

백준 1874 스택 수열 

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

문제를 이해하는데만 2시간이 걸린 것 같다. 

내 생각엔 저 문제만으로는 절.대.로 이해할 수 없다. 💢

 

아래 글들과 내용들을 참고해야 이해할 수 있다.

https://hongcoding.tistory.com/39

https://www.youtube.com/watch?v=byCxMbgzEVM   

 

문제 설명

이 문제는 스택의 FILO의 개념을 익히는데 도움을 주는 문제이다.

주어진 인풋값과 동일해질때까지 스택에 숫자를 append해가고,

동일해진다면 스택에 쌓인 수를 pop 해준다.

만약 인풋값이 스택에서 pop할 수 있는 마지막 숫자가 아니라면 에러를 뿜게된다. 

! pop(0)안되죠~ 무조건 맨 마지막 원소를 pop해야한다.

 

 

풀이 설명

준비물

stack = []

answer = []

cur = 1

 

1. n번을 돌며 인풋값을 받는다.

2.현재 인풋값이 cur과 같아질때까지 반복

  stack.append(cur)

  answer.append('+')

  cur += 1  (*이부분의 순서 중요 아래 코드에 설명)

if stack[-1] == 인풋값이라면: 

  stack.pop()

  answer.append('-')

else:

   print("NO")

 

 

참고 코드

import sys
def solution(n):
  stack = []
  answer = []
  flag = 0 # 중단된 반복문인지 알기위해
  cur = 1 # 1로 시작해야함. :10에서 스택에 쌓을 더하기를 실행할 때 1부터 쌓아줘야함.
  for i in range(n):
    num = int(sys.stdin.readline());
    while cur <= num:
      stack.append(cur)
      answer.append('+')
      cur += 1 
      # 꼭 append이후에 실행해야 함. :9에서 값 비교할때의 값과 stack[-1]의 값이 동일해야함. 
      # 위의 그림에서 파란색 cur = $ 부분 참고 

    print(stack, cur)
    if stack[-1] == num:
      stack.pop()
      answer.append('-')
    else: 
      # stack[-1]값부터 pop을 해줘야 하는데, 인풋값이 stack[-1]과 다르다면
      # FILO 스택의 순서에서 어긋남. 스택이 스택이 아니게됨.
      print("NO")
      flag = 1
      break

  if flag == 0:
    for i in answer:
      print(i)
  
N = int(sys.stdin.readline())
solution(N)

코드출처: https://hongcoding.tistory.com/39