[Python] 1874번 스택 수열

https://www.acmicpc.net/problem/1874

1874번: 스택 수열

---

22/08/28

 

마찬가지로 클래스 2++에 해당하는 문제 중 풀지 않은 문제가 있어서 풀은 문제이다.

 

문제 풀이 자체는 그렇게 마구 어렵다거나 그러지는 않는데 문제 해석이 조금 난감했던 문제이다.(내 국어 능력이 부족한 탓 일 수도 있다.)

 

하지만, 여러 번 틀렸다거나 그러지는 않았고 한 번에 맞았다.

 

지금 되돌아 보니 문제를 좀 더럽게 푼 것 같기도 하다.

 

---

 

문제 해석:

 

 

스택 수열이 주어지면, 그 스택 수열을 만들 수 있는가 여부를 따져서, 만들 수 있다면 그 방법을, 만들 수 없다면 NO를 출력하는 문제이다.

 

당장 스택 수열을 어떻게 만드는지 예제 입력 1과 예제 출력 1을 통해 알아보자.

 

아래 그림은 예제 출력 1의 앞에 10개의 과정을 그림으로 나타낸 것이다.

 

스택 수열을 만드는 과정

이 그림에서 가운데에 파란 글씨로 '+'라고 적혀 있는 것은 왼쪽 스택에 숫자를 추가하는 과정이다.

 

이때, 왼쪽 스택에 숫자를 추가를 할 때, "지금까지 나왔던(자기 자신도 포함하여) '+' 연산자의 횟수"를 추가해준다.

 

예를 들자면, 지금까지 '+' 연산자가 5번 나왔다면 왼쪽 스택에 5를 추가하는 식이다.

 

'-'라고 적혀져 있는 것은 왼쪽 스택에서 하나를 빼서 오른쪽 스택에 추가하는 과정이다.

 

결국 오른쪽 스택을 다 완성하면, 오른쪽 스택이 스택 수열로 완성이 된다.

 

문제를 다음과 같이 이해를 하고 나니, 그냥 간단하게 시뮬레이션을 돌리면서 구현만 하면 되는 부분이었다.

 

---

 

문제 접근 방법:

 

 

이제 문제 해석도 했으니, 어떻게 "NO"를 출력할지 그 부분을 신경 써야 했다.

 

먼저, 나는 "스택 수열에서 제일 큰 숫자가 나오면 그 이후의 숫자는 내림차순이 돼야 한다"라고 생각했다.

 

왜냐하면, 지금까지 등장한 +의 횟수가 왼쪽 스택에서 숫자로 추가될 텐데, 이 성질 때문에 왼쪽 스택에 남아있는 숫자들은 모두 항상 오름차순으로 정렬이 되어있다.

 

스택 수열에서 제일 큰 숫자가 나왔다는 뜻은, "왼쪽 스택에서 제일 큰 숫자가 pop 되어서 오른쪽 스택에 추가되었다"라는 뜻이고, 이후에 남은 행동은 "왼쪽 스택에서 숫자를 모두 빼는 행동" 밖에 할 수 없으므로, 그 뒤에 pop 되는 숫자들은 왼쪽 스택의 반대 순서인 내림차순이 될 수밖에 없다는 것이다.

 

이러한 사실을 예제 입력 1번의 관찰을 통해서 얻어냈다.

 

근데 예제 입력 1번의 숫자를 바꿔서 더 관찰해보니 그렇게 걸러도 불가능한 경우를 찾아낼 수 있었다.

 

그래서 위에서 문제 해석한 것을 토대로 반복해 시뮬레이션을 돌리다가 일정 횟수 이상을 넘어가면 불가능하다고 판단했다.

 

그 일정 횟수는 20만을 조금 넘어가는 숫자로 정했다.

 

그 이유는 다음과 같다.

 

먼저, 수열의 길이 제한은 10만이어서 최대로 입력받았을 상황을 가정했다.

 

다시 말해, 나는 연산자를 여러 번 반복 적용하여 10만짜리 크기의 수열을 만들어야 한다.

 

즉, 왼쪽 스택에 적용되는 연산자인 +연산자(push)가 10만 번 적용 되야하고, 왼쪽 스택에서 원소를 빼서 오른쪽 스택으로 옮기는 연산자인 -연산자(pop)가 10만번 적용돼야 한다는 뜻이다.(완성된 오른쪽 스택이 스택 수열이기 때문에)

 

그래서, 두 연산자의 적용 횟수를 합치면 최대 20만 번 이기 때문에 이 적용 횟수를 넘겨도 오른쪽 스택이 스택 수열과 똑같아지지 않는다면 불가능하다고 판단했다.

 

---

이 접근 방법과 문제 해석을 토대로 한 나의 코드이다. 더보기를 누르면 확인할 수 있다.

# 1874번 스택 수열
# 자료구조, 스택
'''
접근 방법:
불가능한 경우를 빠르게 판단하기 위해 초반에 스택수열을 입력 받을때 불가능한 경우를 걸러냈다.
스택 수열의 특성 상 제일 큰 수가 나온 뒤에는 항상 내림차순으로 내려갈 수 밖에 없다.
왜냐하면, 최대 원소가 나온 뒤로는 계속 pop을 할 수밖에 없는데,
애초에 스택을 쌓을 때 크기순으로 쌓이기 때문에 pop만 하면 이전보다 작은 수가 나올 수 밖에 없다.

이후 가능한 경우 중 다 가능한 것이 아니므로,
반복하여 시뮬레이션 하다가 반복 횟수가 일정횟수를 넘어가면 불가능한 것으로 판단함.
그 이유는 N의 최댓값이 10만인데, pop과 append횟수를 다 합치면 10만 + 10만이므로
넉넉하게 20만 조금 넘겨서도 반복을 했는데도 스택수열이 만들어지지 않으면
불가능 한 것으로 판단한다.
'''
import sys
input = sys.stdin.readline

n = int(input())
stack_seq = []  # 스택 수열
max_ele_appear = False  # 최대 원소가 등장했는가?
possible_flag = True   # 스택 수열을 만들 수 있는가?
before_ele = n   # 이전 원소를 저장하는 변수. 최대 원소가 등장한 이후부터 써먹으므로 n으로 초기화.
for _ in range(n):
    k = int(input())
    if max_ele_appear and before_ele > k: # 최대 원소가 나타난 뒤 내림차순이면
        before_ele = k   # 그대로 이전 원소를 현재 원소로 갱신
    elif max_ele_appear and before_ele < k: # 최대 원소가 나타난 뒤에 내림차순이 아니면
        possible_flag = False  # 불가능함
        break  # 입력 중단
    if k == n:   # 최대 원소가 나타나면 플래그를 세움
        max_ele_appear = True
    stack_seq.append(k)

if not possible_flag:
    print('NO')
else:
    loop_count = 0  # 루프 횟수 세어주는 변수
    op_stack = []  # 연산자를 여기에 저장
    plus_count = 0  # 지금까지 +가 몇 번 나왔나 저장
    index = 0  # 스택 수열의 인덱스를 가르키는 포인터
    stack_1 = []  # 이 스택에서 pop을 하면
    stack_2 = []  # 그 원소가 여기로 간다.(스택 수열이 여기서 만들어 진다.)
    while True:
        if stack_2 == stack_seq:  # 스택 수열이 만들어지면 ok
            break
        if loop_count >= 200500:  # 일정 루프를 초과하면 ㄴㄴ
            possible_flag = False
            break
        if stack_seq[index] > plus_count:  # 지금까지 나온 plus 숫자가 스택수열 숫자보다 작으면
            plus_count += 1
            op_stack.append('+')
            stack_1.append(plus_count)
        elif stack_seq[index] == plus_count or stack_1[-1] == stack_seq[index]:
            op_stack.append('-')
            stack_2.append(stack_1.pop())
            index += 1
        loop_count += 1
    if possible_flag:
        for op in op_stack:
            print(op)
    else:
        print('NO')