[백준/Python] 1847번 스택 수열

---

문제

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

---

문제 이해

숫자 1부터 n까지의 수를 차례대로 push하는데 push와 pop을 이용해서 원하는 배열을 만드는 문제이다.

이해하기 쉽게 chatGPT의 도움을 받았다.

 

📌 예시 ] 단계별로 스택의 변화를 보자

- 수열 [4, 3, 6, 8, 7, 5, 2, 1] 만들기

연산	스택 상태	출력 수열(pop)
push 1	[1]
push 2	[1, 2]
push 3	[1, 2, 3]
push 4	[1, 2, 3, 4]
pop	[1, 2, 3]	4
pop	[1, 2]	3
push 5	[1, 2, 5]
push 6	[1, 2, 5, 6]
pop	[1, 2, 5]	6
push 7	[1, 2, 5, 7]
push 8	[1, 2, 5, 7, 8]
pop	[1, 2, 5, 7]	8
pop	[1, 2, 5]	7
pop	[1, 2]	5
pop	[1]	2
pop	[]	1

---

문제 풀이(정답)

n = int(input())

stack = []

ans = []

now = 1

find = True

for i in range(n):

    su = int(input())

    while now <= su:

        stack.append(now)

        ans.append('+')

        now += 1

    if stack[-1] == su:

        stack.pop()

        ans.append('-')

    else:

        find = False

if not find:

    print('NO')

else:

    print(' '.join(ans))

 

stack : 스택 역할

ans : 정답, 결과

now : 1부터 n까지 증가하면서 push할 숫자

find : 문제에서 주어진 수열을 만들 수 있는지 체크하는 변수

 

while문을 이용해 필요한 숫자가 올 때까지 push를 하고, stack의 마지막값이 su라면 pop을 진행한다.

그리고 stack의 마지막 값이 su가 아니라면 find 값을 False로 바꾸고 출력을 할 때 NO라고 출력하고 그렇지 않는다면 정답 리스트를 출력해준다.

 

+ sys모듈을 사용하지 않아도 정답이 되지만 sys모듈을 사용하면 훨싼 빠르게 코드를 수행할 수 있다.