공부 자료/알고리즘
(Python/파이썬) 백준 1874번 - 스택 수열
뚜루뚜루세니
2021. 8. 19. 13:18
728x90
문제출처: https://www.acmicpc.net/problem/1874
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
1. 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
import sys
n = int(sys.stdin.readline())
arr =[] #입력값 순서대로 담을 배열
stack=[] #스택으로 활용
ans=[] #push,pop기록
for _ in range(n):
arr.append(int(input())) #n개 인풋 배열에 저장
index = 1
for i in range(n):
if arr[i] >= index:
while index <= arr[i]:
stack.append(index)
ans.append("+")
index+=1
stack.pop()
ans.append('-')
else:
if len(stack)!=0 and stack[-1] == arr[i]:
stack.pop()
ans.append('-')
if len(stack) != 0:
print("NO")
else:
for i in ans:
print(i)
|
cs |
2. 해결과정
스택을 이용한 문제였다.
문제 자체의 문장이 이해하기가 좀 어려웠는데,
입력예시를 살펴보면 4 3 6 8 7 5 2 1 순으로 수열을 받아오는 것을 확인할 수 있다.
순서대로 첫번 째 입력값이 8까지의 숫자를 스택에 넣고 빼면서 위의 배열을 완성시켜주면된다.
1) 각 수열의 값에 도달할 때까지 1부터 차례대로 스택에 넣고 + 기호 기록
2) 입력된 수열 값이 차례대로 넣고 있었던 수보다 작으면 stack 가장 위 해당 수열 값 있는지 찾기
3) 해당 수열값과 같으면 pop -> - 기록 아니라면 NO 출력
3. 느낀점
문제를 이해하는 것에서 어려웠다..
728x90