백준 : 스택 수열 - 1874

 

예제 입력 1 

8
4
3
6
8
7
5
2
1

예제 출력 1 

+
+
+
+
-
-
+
+
-
+
+
-
-
-
-
-

예제 입력 2 

5
1
2
5
3
4

예제 출력 2 

NO

 

우리의 목표는 주어진 수열의 각 숫자를 차례대로 만드는 것이다. 스택에 숫자를 넣을 때는 1부터 오름차순으로만 넣을 수 있다. 즉, 1을 넣었다면 다음에는 2, 그 다음에는 3..이런식으로 순서대로 넣어야 한다.

주어진 수열의 숫자를 하나씩 보면서 아래 과정을 반복해야 한다.

1. 필요한 숫자를 준비한다.

- 스택에 아직 없는 목표 숫자가 있다면, 오름차순 규칙에 따라 그 숫자가 스택의 맨 위에 올 때까지 순서대로 숫자를 넣는다(push).
이 과정에서 스택에 넣는 모든 숫자는 +로 기록한다.

2. 목표 숫자를 꺼낸다
- 스택의 맨 위 숫자가 목표 숫자와 일치하면, 그 숫자를 스택에서 꺼낸다(pop).
이 과정은 -로 기록한다.

3. 불가능한 경우 판단
- 만약 스택의 맨 위에 있는 숫자가 목표 숫자보다 크다면, 주어진 수열을 만들 수 없다. 스택은 맨 위에 있는 숫자만 꺼낼 수 있기 때문에, 목표 숫자보다 큰 숫자를 먼저 꺼내야 하는 모순이 발생하기 때문이다. 이 경우, 곧바로 "NO"를 출력하고 종료한다.

[최종 결과]
위 과정을 주어진 수열의 모든 숫자에 대해 성공적으로 반복하면, 기록해 둔 +와 - 연산을 순서대로 출력한다. 만약 도중에 불가능하다고 판단되면 "NO"를 출력한다.

여기서 중요한 것은 우선, stack으로 기록할 것과, +,-인지 판단할 기록, 그리고 되지 않았을 때를 판단할 변수 등이 필요하다. 

우선 n은 수열의 크기, stack은 스택 역할을 할 리스트, current는 스택에 다음에 넣을 숫자(1부터 시작), result는 연산 기록, is_valid는 성공 여부를 나타내는 변수로 사용하였다.  수열의 각 숫자인 target_number를 하나씩 입력받아 아래의 과정을 반복한다.

[Push]

current가 target_number보다 작거나 같은 동안, current를 스택에 넣고(push, + 기록), current 값을 1 증가시킵니다. 이 과정은 오름차순 push 규칙을 지키는 방법이다.
[Pop]

스택의 맨 위 숫자가 target_number와 같으면, 스택에서 그 숫자를 빼고(pop, - 기록) 다음 target_number로 넘어갑니다.
실패: 만약 스택의 맨 위 숫자가 target_number와 다르면, 이는 주어진 수열을 만들 수 없는 경우이다. is_valid를 False로 바꾸고 반복문을 멈춘다.

최종 출력: 모든 숫자를 성공적으로 처리했으면(is_valid가 True), result에 기록된 연산들을 출력하게 하고. 실패했다면 "NO"를 출력하도록 한다.

import sys

n = int(input())
stack = []
current = 1
result = []
is_valid = True

for _ in range(n):
    target_number = int(input())

    while current <= target_number:
        stack.append(current)
        result.append("+")
        current += 1
    
    if stack[-1] == target_number:
        stack.pop()
        result.append("-")
    
    else:
        is_valid = False

if not is_valid:
    print("NO")
else:
    for i in result:
        print(i)

 

https://anggeum.tistory.com/entry/%EB%B0%B1%EC%A4%80-1874%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%8A%A4%ED%83%9D-%EC%88%98%EC%97%B4-%ED%92%80%EC%9D%B4-%EB%B0%8F-%EB%8B%B5%EC%95%88

[백준 1874][Stack][파이썬] 스택 수열 - 풀이 및 답안

 

참고로 이 분이 노트에 정리한 것이 있는데 이를 참고하면 도움이 될 것 같다. 나도 초반엔 문제 해석을 못 해서 어떻게 풀어야 할지 감이 안잡혔었다. 그래서 노트에 기록을 하면서 하니까 이해가 이전보다 잘 되어서 문제를 풀 수 있었다.