탑

문제

풀이

그래프를 그리면 문제를 쉽게 이해할 수 있다.
6은 수신받을 탑이 존재하지 않으므로 0이 된다.
9는 6이 있지만 낮으므로 0이 된다.
5는 9가 있으므로 2가 된다.
7은 9가 있으므로 2가 된다.
4는 7이 있으므로 4가 된다.

처음에 2중 포문으로 찾으려고 했지만 시간초과가 발생하였다.
왜냐하면 2중 포문으로 하게 될 시 대략 2500억 이 되는 연산을 하게 된다.

다른 풀이를 찾아보았다.
stack을 이용하는 것이다.

6 => 스택에 6 push s
stack = [6]
9 => 기존 스택 top은 6이다 9가 더 크게 되므로 기존 6은 pop, 9는 push
stack = [9]
5 => 기존 스택 top은 9이다. 5는 9보다 작으므로 스택은 그대로 두고 5를 push
stack = [9, 5]
7 => 기존 스택 top은 5이다. 5는 7보다 작으므로 수신 될 수 없으므로 pop을 해준다. 9는 수신될 수 있으므로 그대로 둔다.
stack = [9, 7]
4 => 기존 스택 top은 7이다. 7은 4보다 크므로 수신될 수 있다. 그대로 push 해준다.
stack = [9, 7, 4]

여기서 핵심은 수신탑을 찾을때까지 pop을 해주는 것이다.

이것을 코드로 나타내보자

코드

for test_case in range(1):
    n = int(sys.stdin.readline())
    tmp = list(map(int, sys.stdin.readline().split()))
    height = []

    for i in range(1, n + 1):
        height.append([tmp[i - 1], i])

    stack = []
    height.reverse()
    ans = []
    for i in range(n):
        h, idx = height.pop()
        flg = True

        if not stack:
            stack.append([h, idx])
            ans.append(0)
            continue

        while stack:
            top_h, top_idx = stack[-1]

            if top_h >= h:
                ans.append(top_idx)
                flg = False
                break

            stack.pop()
        if flg:
            ans.append(0)
        stack.append([h, idx])
    print(' '.join(map(str, ans)))