Baekjoon 문제 풀기 (1874번 : 스택 수열) Python

1874번 : 스택 수열

1. 문제읽기

---

기초적인 스택 문제

스택의 개념은 알고 있었는데 구현이 어려웠다.
스택을 파이썬으로 구현하는 방법이 기억나지 않아서 실패했다..

retry 가 쌓여간다~!!!

2. 제출 코드

---

나름 포인터를 써서 풀어보려고 했는데, 그냥 스택으로 풀면 되는 문제였다.
다음에 다시 풀어봐야겠다.

제출 못한 실패 코드..

import sys

n = int(sys.stdin.readline().rstrip())

stack = []
for i in range(1, n+1):
	stack.append(i)
# stack = [1, 2, 3, 4, 5, 6, 7, 8]
p = 0  # 포인터
ans = ["+"]

while p != len(stack)-1:
	target = int(sys.stdin.readline().rstrip())
	if stack[p] < target:
		p += 1
		ans.append("+")
	elif stack[p] > target:
		p -= 1
		ans.append("+")
	elif stack[p] == target:
		stack.remove(stack[p])
		p -= 1
		ans.append("-")


if len(stack) != 0:
	print(-1)

else:
	print(ans, sep=' ')

3. 공부할 것

---

파이썬에서 stack은 리스트로 구현할 수 있다.
push는 append 메소드로, pop은 그냥 pop을 쓰면 된다.
while num <= target 이 코드가 어려웠는데, 복잡하게 생각하지 말고 target 숫자보다 num이 작으면 계속 push해서 넣어줘야하는 거다.
num이 target보다 커지면, 스택의 마지막 숫자가 target과 같은지 확인하고 같다면 꺼내준다.
만약 같지 않다면 스택 구조로 만들 수 없는 숫자이기 때문에 NO를 출력한다.

import sys

n = int(sys.stdin.readline().rstrip())
num = 1
ans = []
stack = []
is_stack = True

for _ in range(n):
    target = int(sys.stdin.readline().rstrip())
    while num <= target:
        stack.append(num)
        ans.append("+")
        num += 1
    if stack[-1] == target:
        stack.pop()
        ans.append("-")
    else:
        is_stack = False

if not is_stack:
    print("NO")
else:
    print(*ans, sep="\n")