문제
스택은 기본 데이터 구조 중 하나이며 컴퓨터 프로그램을 작성할 때 자주 사용되는 개념입니다.
스택에는 데이터를 삽입(푸시)하고 데이터를 팝(팝)하는 입구가 동일합니다.
후입선출(LIFO)은 후입 데이터의 특성입니다.
1에서 n까지의 숫자를 스택에 쌓았다가 꺼내서 일련의 숫자를 만들 수 있습니다.
이때 스택에 밀어넣는 순서는 반드시 오름차순이라고 가정하자.
임의의 시퀀스가 주어지면 스택을 사용하여 시퀀스를 생성할 수 있는지 여부,
그렇다면 푸시 및 팝 작업을 수행하는 데 필요한 순서를 파악할 수 있습니다.
계산하는 프로그램을 작성하세요.
입력
첫 번째 줄은 n(1 ≤ n ≤ 100,000)을 제공합니다.
두 번째 줄부터 n개의 줄에는 수열을 구성하는 1부터 n보다 작은 n까지의 정수가 순서대로 하나씩 주어진다.
물론 같은 정수는 두 번 나타나지 않습니다.
인쇄
입력 시퀀스를 만드는 데 필요한 작업을 한 줄에 하나씩 출력합니다.
푸시 작업은 +로 표시되고 팝 작업은 -로 표시됩니다.
불가능한 경우 NO를 출력한다.
설명
건너뛸까 하다가 스택 부분에서 마지막 문제라서 적어두기로 했습니다.
내 경우에는 문제 번호 1874를 읽기만 해도 그가 도대체 무슨 말을 하는지 이해할 수 없었다.
예를 들어 보겠습니다.
첫 번째 줄에 n이 주어지면 1에서 n까지의 숫자를 스택 방식으로 넣고 팝아웃할 수 있는지 알아내야 합니다.
예제에서 첫 번째 숫자 4의 경우 스택이 비어 있으므로 1, 2, 3, 4를 순서대로 넣고 4를 꺼냅니다.
동작 순서는 ‘+ + + + -‘가 됩니다.
그러면 3의 경우 이미 스택에 있으므로 바로 숫자를 빼내고 ‘-‘만 추가한다.
다음의 경우인 6의 경우 현재 스택에 있는 숫자는 (1, 2)이므로 이미 사용된 3, 4는 생략하고 5, 6을 더한다.
6은 빼야 합니다.
따라서 연산에 ‘+ + -‘를 추가합니다.
이런 식으로 끝까지 가야합니다.
그리고 스택에 (1, 2)가 있고 1을 꺼내려고 하면 방법이 없기 때문에
‘NO’를 인쇄하고 프로그램을 종료합니다.
특정 숫자가 주어지면 몇 자릿수를 더 입력해야 합니까?
주어진 숫자 – 스택에 남아 있는 숫자의 수 – 작업에서 ‘-‘가 사용된 횟수
를 사용하여 계산한 결과 통과했습니다.
코드는 다음과 같습니다.
import sys
n = int(sys.stdin.readline().rstrip())
stack = ()
result = ()
cnt = 0
for _ in range(n):
num = int(sys.stdin.readline().rstrip())
if len(stack) == 0:
m = num - cnt
for i in range(m - 1, -1, -1):
stack.append(num - i)
result.append('+')
result.append('-')
cnt += 1
stack.pop()
else:
if num < stack(-1):
print('NO')
sys.exit()
elif num == stack(-1):
result.append('-')
cnt += 1
stack.pop()
elif num > stack(-1):
m = num - len(stack) - cnt
for i in range(m - 1, -1, -1):
stack.append(num - i)
result.append('+')
result.append('-')
cnt += 1
stack.pop()
print(*result, sep='\n')