1874번 스택 수열
처음에 문제를 이해하는데 시간이 걸렸다.
1~n 까지의 숫자가 나열되어있고 (수열 리스트 1번)
1~n의 숫자가 임의의 수열로 주어진다.(수열 리스트 2번)
2번 수열과 같은 수열이 될 수 있도록 1번 수열에서 차례대로 꺼내
스택 구조로 어딘가에 담다가 꺼내는 행동을 반복한다.
이때 담을 때는 '+' 출력 꺼낼때는 '-'를 출력한다.
만약 2번 수열이 해당 방법으로 만들 수 없는 수열이라면 'NO'출력하는 문제.
예제 입력 1을 예를 들어 n이 8이라면 1,2,3,4,5,6,7,8이 1번 수열 리스트가 되고
4,3,6,8,7,5,2,1 수열이 2번 수열 리스트가 된다.
1번 수열에서 차례대로 꺼내 담다가 2번 수열의 처음 숫자인 4가 담기면
꺼내고 그 다음 숫자와 비교해 같으면 또 꺼내고 아니면 다시 다음 숫자를 담아준다.
이 때 처음 1,2,3,4 까지 담긴 과정으로 '+'가 4번 출력되고 4와 3을 꺼냈으니 '-'가 2번 출력된다.
이 후 과정을 반복 하면 담기는 곳은
1,2,3,4 -> 1,2 -> 1,2,5,6 -> 1,2,5 -> 1,2,5,7,8 -> 모두 꺼내짐
즉, 네개 담고 -> 두개 꺼내고 -> 두개 담고 -> 한개 꺼내고 -> 두개 담고 -> 다섯개를 꺼낸 것이 된다.
이 것을 기호로 바꿔보면
'+''+''+''+'-> '-''-' -> '+''+' -> '-' -> '+''+' -> '-''-''-''-''-' 가 출력 되어야 한다.
import sys
input = sys.stdin.readline
num = int(input())
n = [i for i in range(num,0,-1)] # 1~num 까지의 숫자 역순 나열
m = [int(input()) for _ in range(num)] # 입력되는 num개의 숫자 리스트 생성
stack = [] # n에서 꺼내 담았다가 m과 같은 수열대로 숫자를 내보내기 위한 빈 리스트
cnt = [] # 출력 할 기호 쌓아줄 빈 리스트
a = 0 # m의 인덱스 1씩 더해줄 예정
while 1:
for i in n: # 리스트 n 순회
stack.append(n.pop()) # n의 마지막 숫자를 꺼내 stack에 담아준다.
cnt.append('+') # 담을 때는 '+'를 출력해야 함으로 '+' 쌓기
if stack[-1] == m[a]:
# 만약 담아둔 숫자의 마지막 숫자와 m의 a 인덱스와 같다면
while 1:
stack.pop() # 담아둔 숫자의 마지막 숫자 꺼내기
cnt.append('-') # 꺼낼때는 '-'를 출력해야 함으로 '-' 쌓기
a += 1 # m의 그 다음 인덱스에 있는 수와 비교하기 위해 +1
if len(stack) == 0: # 만약 담아둔 숫자가 없거나
break
elif stack[-1] != m[a]:
# 담아둔 숫자들의 마지막 숫자가 비교 숫자와 다르다면
break # break
if len(n) == 0: # 위의 계산식을 n 리스트에 요소가 남아있지 않을 때 까지 반복
break
if len(stack) != 0:
# n 리스트에 담겨있던 숫자를 모두 꺼냈는데
# stack에 담아둔 숫자가 모두 꺼내지지 못했다면
print('NO') # stack 으로 만들 수 없는 수열 'NO' 출력
else: # stack에 담아뒀던 숫자들이 모두 꺼내졌다면
print(*cnt,sep='\n') # 쌓아둔 기호를 한개 한개 출력이해를 하는 데 시간이 걸린만큼 사족이 많이 붙게 된 문제였다..ㅎㅎ
