알고리즘
스택 #백준 1874
현쥬스주스
2021. 3. 18. 20:38
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
[ 문제 해결 방법 ]
처음 문제를 보고 무슨말인지 하나도 이해하지 못하였다.. 결국 인터넷 검색을 통하여 문제를 이해하였다.
8 4 3 6 8 7 5 2 1
위와 같이 입력을 받는다고 하자.
n이 8이고 수열 = [4, 3, 6, 8, 7, 5, 2, 1] 이 된다.
그럼 이제 1 부터 8 까지 오름차순으로 숫자를 받아서 스택을 활용해 수열 = [4, 3, 6, 8, 7, 5, 2, 1]을 만들어 주면 된다.
우선 스택에 push를 먼저 하면 1이 담긴다.
s = [1]
한번 더 push를 하면 2가 담긴다.
s = [1, 2]
이런식으로 push를 4번해주면
s = [1, 2, 3, 4]가 담긴다.
여기서 입력받은 수열과 같게 하려면 pop을 두번 해주면
[4, 3] 이렇게 담겨진다.
이런식으로 push와 pop을 해가며 pop을 이용해 입력받은 수열([4, 3, 6, 8, 7, 5, 2, 1])을 만드는 것이다.
문제만 이해한다면 쉽게 풀 수 있다.
[ 소스코드 ]
n = int(input())
s = []
op = []
count = 1
temp = True
for i in range(n) :
num = int(input())
while count <= num :
s.append(count)
op.append("+")
count += 1
if s[-1] == num :
s.pop()
op.append("-")
else :
temp = False
break
if temp == False:
print('NO')
else:
for i in op:
print(i)