[Baekjoon 2493 / python / 골드5] 탑

import sys

n = int(sys.stdin.readline()) # 탑 개수

towerList = list(map(int, sys.stdin.readline().split())) # 탑 목록

result = [0] * n # 결과 리스트

stack = [] # 후보 탑을 저장할 스택

for i in range(n):

    while stack:

        if towerList[stack[-1][0]] < towerList[i]:  # stack의 후보가 현재 탑보다 낮으면 pop 한다

            stack.pop()

        else:

            result[i] = stack[-1][0] + 1  # stack의 후보가 레이저를 받으면 result에 추가한다

            break

    stack.append((i, towerList[i])) # 현재 탑을 stack에 추가한다 ( 다음 탑이랑 또 비교해야 하니까 )

print(*result)

 

스택을 사용하는 문제이다. 스택에서 무의미한 탑을 계속 제거해가며 비교군을 줄여 해결해야 하는 문제다.

 

해결한 후에, "왜 이 당연한 걸 생각 못 했지?" 라는 생각이 들었고, 이해했다고 생각한 후에도 한참 뒤에 생각나서 갑자기 "아니 이거 스택으로 하든 반복문으로 하든 효율 똑같은 거 아닌가?" 라는 생각이 들며 한참동안 혼란스러웠다.

 

탑이 내림차순 ( 10 9 8 7 6 5 4 ... ) 순으로 되어 있을 땐, 현재 탑이 "9"라고 가정하면 반복문이든 스택이든 비교해야 하는 횟수가 똑같다.

하지만 예를 들어 탑이 오름차순이고 높은 탑이 맨 앞에 있다면? ( 10 1 2 3 4 5 6 7 8 ) 

반복문은 8 7 6 5 4 ... 이렇게 다 비교해야 하지만, 스택은 이미 8 앞의 무의미한 탑인 1234567이 지워진 상태이기 때문에 비교할 횟수가 엄청나게 줄어든다.

 

원리는 어렵지 않은데 이상하게 계속 헷갈리는 문제였다.