약 1년전 한창 군머에서 제설하고 있을때 풀었던 스택 수열 문제를 다시 풀어보았습니다. 스택 수열은 '스택'주제와 관련된 문제이며 링크는 아래 첨부하겠습니다.
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 : n의 값
- n개의 줄에 수열을 이루는 1이상 n 이하의 정수가 하나씩 주어진다
- 출력
- 수열을 만들기 위해 필요한 연산을 한줄에 한개씩 추가한다.push는 +로, pop은 -로 표현하며, 구현이 불가능한 경우에는 NO를 출력한다
문제를 요약해 보면 1부터 n까지의 수를 순서대로 스택에 넣어야 되는 규칙을 지키면서, push, pop을 이용해서 주어진 수열을 구현할 수 있는지에 질문하는 문제이다.
위 예제입력/출력 1을 기준으로 그림으로 설명을 해보면 아래와 같이 나타낼 수 있다.
또다른 예제 입/출력 2로 유도를 해보면
이 알고리즘의 프로세스를 유도해 보겠습니다. 우선 두개의 스택이 필요합니다. 하나는 정답(+,-기호가 담긴)을 위한 스택(s1)과 다른 하나는 단계별 스택의 변화를 관찰하기 위한 스택(s2)입니다(위 그림에서 각과정 마다의 '스택'에 해당한다고 보시면 됩니다). 또한 마지막으로 어떤 값을 넣었는지를 보기위한 변수를 선언합니다. 이 값은 0부터 시작하고, 값을 s2에 넣을때는 이 값에 + 1을 하여 스택에 넣는 방식으로 하였습니다.
기본적으로 가져야 할 조건은, 주어진 수열의 각 요소를 검사하면서 프로세스를 가져야 한다고 생각했습니다. 각 수열 요소의 순서에 맞게끔 push, pop연산을 엮어줘야하기 때문입니다. 그리고 세가지의 검사 조건이 필요하다고 보았습니다.
- 만약 마지막에 넣은 값이 검사중인 요소보다 작은 값이라면, 검사중인 요소와 동일한 값일때까지 push를 해줍니다. 그리고 s1에 '+'를 넣어준 요소의 개수만큼 넣어줍니다.
- 만약 s2의 마지막 원소값이 검사중인 요소와 일치하지 않는다면, 이는 성립될 수 없는 수열입니다.
- 기본적으로 이 스택에는 순서대로 push/pop이 이루어져야 합니다. 그렇기 때문에, 마지막 값과 일치하지 않을 경우에는 순서대로 push/pop이 이루어지지 않은 수열이므로 구현할 수 없는 수열로 판단합니다
- 만약 s2의 마지막 원소값이 검사중인 요소와 동일한 경우 s1에 '-'를 넣고, s2에 pop연산을 1회 실행해줍니다.
구현은 아래와 같습니다.
'''
첫째줄 : n 이 주어진다
둘째줄 : n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 주어진다
'''
import sys
from collections import deque
def solve(max,seq) -> None:
'''
max : 스택의 최대 크기
seq : 만들려는 수열을 의미한다
'''
answer = []
stacks = []
last_input = 0
#최초실행 판별
first = True
for i in seq:
while last_input < i:
stacks.append(last_input + 1)
answer.append('+')
last_input += 1
if i != stacks[-1]:
print("NO")
return
if stacks[-1] == i:
answer.append('-')
stacks.pop()
print(*answer,sep='\n')
if __name__ == "__main__":
#스택 원소 개수
max = int(input())
#수열 형태
sequence = [int(input()) for _ in range(max)]
solve(max,sequence)