백준: 2493 탑

문제

2493번: 탑

 

문제 풀이

 좌측에 있는 탑이, 우측의 탑 보다 높이가 높은 경우에 신호를 수신할 수 있다. 이를 구현하기 위해 처음에는 입력을 리스트로 받고 뒤집어서 생각해야 할까 고민했다. 하지만, 각 탑의 인덱스, 높이를 `stack`으로 처리하면 위 문제를 간단히 해결할 수 있다.

 

• `stack`에 탑을 순서대로 삽입한다.
  • pop을 하게 되면, 현재 탑을 기준으로 바로 좌측의 탑부터 비교를 시작 할 수 있다.
• 현재 타워와 비교하여 `stack`안의 타워들(좌측의 타워들)과 비교하여, 높이가 낮다면 제거한다.
  • 현재 타워보다 높이가 낮다면 필요 없는 값이기 때문이다.
• 위의 값을 순차적으로 반복하면, 원하는 답을 찾을 수 있다.

 

코드

from sys import stdin

IDX, HEIGHT = 0, 1

if __name__ == "__main__":
    N = int(stdin.readline())
    tower = list(map(int, stdin.readline().split()))
    stack = []
    answer = [0 for _ in range(N)]

    for idx, height in enumerate(tower):
        while stack:
            if stack[-1][HEIGHT] > height:
                answer[idx] = stack[-1][IDX] + 1
                break
            else:
                stack.pop()

        stack.append((idx, height))

    print(' '.join(map(str, answer)))