[BOJ](Phython) 1874번 : 스택 수열

www.acmicpc.net/problem/1874

1874번: 스택 수열

n = int(input())
arr = [int(input()) for _ in range(n)]

idx = 0
cur = 1
stack = []
answer = []
while idx < len(arr):
    if stack:
        if stack[-1] == arr[idx]:
            stack.pop()
            idx += 1
            answer.append("-")
        elif stack[-1] < arr[idx]:
            stack.append(cur)
            answer.append("+")
            cur += 1
        else:
            answer = []
            answer.append("NO")
            break
    else:
        stack.append(cur)
        answer.append("+")
        cur += 1

for i in answer:
    print(i)

 

stack이 있을 때, stack에 pop을 한 순간이 곧 결과가 되는 배열에 값을 넣는 순간이다.

 

첫 번째 예시에서 정답이 되는 수열은 [4, 3, 6, 8, 7, 5, 2, 1]이다. 즉, stack.pop()을 했을 때 4를 얻어야 하고, 한번 더 pop()을 했을 때 3을 얻어야 한다.

 

먼저 cur = 1 이라는 변수를 만든다. 스택에 존재하는 변수가 무엇인지, 스택에 무엇을 넣어야 할지를 결정하는 변수다.

idx = 0은 결과가 되는 배열의 인덱스이다. 만약 arr[0]에 대해서 pop을 했다면 arr[1]에 대해서 pop을 해야한다. 즉, 스택에서 pop을 해야 할지를 결정할 수 있도록 배열의 값을 참조하는 변수이다.

 

모든 경우에 대해서 stack에 값을 추가한다면 결과 리스트인 answer에 "+"를, 값을 제거한다면 "-"를 추가한다.

 

arr에 있는 모든 변수를 idx를 통해 읽을 때까지 while을 반복하는데, 반복하면서 생기는 경우의 수는 총 4가지이다.

---

1. 스택에 아무것도 없는 경우:

스택에 아무것도 없는 경우 당연하겠지만 스택에 값을 추가해야 한다. 나머지 세가지 경우에 대해서 stack[-1]을 비교하기 위해선 스택에 최소한 1개 이상의 변수가 존재해야 한다.

cur = 1일 때 1을 스택에 넣었다면 cur += 1한다. 이 cur은 스택에 값을 넣었을 때 +=1이 된다. 왜냐하면 문제에서,

스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자.

라고 명시되어있기 때문이다.

 

2. stack[-1] == arr[idx]:

이는 stack.pop()을 해야함을 의미한다. 이후 arr list의 다음 인덱스를 참조하기 위하여 idx += 1을 한다. 

 

3. stack[-1] < arr[idx]:

예를 들어, stack = [1,2]이고 arr = [4,3,~]이고 idx = 0일 때, stack.pop()을 통해 보이지 않는 결과 배열에 그 값을 추가하기 위해선 스택에 3과 4를 추가해야 한다.

따라서 cur을 append()하고, cur += 1한다.

 

4. stack[-1] > arr[idx]:

이는, 주어진 배열을 만들 수 없음을 의미한다. 예제 2번과 같은 경우인데,

결과에 [1,2,5]가 추가 되었다는 것은 스택에 [3,4]가 남아있어야 한다. 스택에 [3,4]가 남아 있을 때, 3,4의 순서로 pop()을 할 수 없으므로 에러이다. 즉,

 

stack = [3,4] 와 arr = [1,2,5,3,4] & idx = 3일 때, stack[-1] > arr[idx] 이므로 answer를 모두 비우고 "NO"를 추가한 후, while을 종료한다.

---

예제 입력 1번의 경우 그림으로 보자.

 스택에 아무것도 없으므로 cur = 1에서 cur을 추가시킨다.

스택에 값을 추가했지만 배열에 4를 추가하기 위해선 스택에 4가 존재해야 한다. 4까지 계속 넣으면 다음과 같다.

이 상황에서 stack.pop()을 하면 보이지 않는 결과 배열에 4를 추가할 수 있다.

결과 배열은 문제에서 요구하지도 않고, 사용하지도 않는다. 그림에선 pop()을 하면서 arr과 비교하기 위하여 만들었다.

이제 idx = 1이 되었고, stack[-1] == arr[1] 이므로 stack.pop()을 한다.

 

이제 idx=2가 되었고, 결과 배열에 6을 넣기 위해선 스택에 6까지 넣어야 한다. 

스택에 6이 있을 때 stack[-1] == arr[2]이므로 결과 배열에 6을 넣기 위해 stack.pop()한다.

idx = 3일 때 arr[3] = 8이므로 스택에 8까지 넣어야 한다.

스택을 보면 알 수 있듯이, stack.pop()을 stack이 비워질때 한다면 8,7,5,2,1 순서로 결과 배열에 들어갈 것이다.

pop()을 했을 때 결과 배열과 비교해야 할 arr이 같다. idx=8이므로 while loop을 종료하고 answer를 출력하면 된다.

---

예제 입력 2

 

스택이 비어있을 때 cur = 1을 stack에 넣으면 stack[-1] == arr[0]이다. 따라서 stack.pop()하여 결과 배열에 추가한다.

 

한개를 넣고 한개를 뺐으므로 스택은 또 비어있다. 따라서 스택에 2를 넣는다.

이는 stack[-1] == arr[1] 이므로, stack.pop()하여 결과 배열에 추가한다.

 

스택이 비어있으므로 stack.append(cur), 이 때 cur = 3이다.

 

stack[-1]은 3인데 arr[2]는 5이다. 따라서 cur = 4, cur = 5를 넣어야 한다. 그 결과는 다음과 같다.

 

stack[-1] == arr[2]이므로 stack.pop()하여 결과 배열에 5를 추가한다.

 

이 때 문제가 발생한다. 스택은 LIFO이므로 반드시 4가 먼저 pop되어야 한다. 하지만 pop하는 순간 결과 배열에 4를 추가하므로 결과 배열과 arr이 달라지게 된다.

 

즉, stack[-1] < arr[3] 일 경우 주어진 arr은 스택과 오름차순 숫자를 이용해 만들 수 없는 배열이다. 

따라서 answer 배열에 원소를 없애고 "NO"를 추가한 뒤, while loop을 break한다.

---

결과