[백준 2024/09/10] 2493번 탑

1. 문제

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

 

2. 접근 방법

2개의 stack을 이용해서 푸는 것이 적절하다고 생각하였다.

 

쏘기 전의 레이저들을 모아놓은 것을 b_shoot이라고 선언하였다.

또한, [높이, 송신탑 번호] 로 저장해 두어, 추후에 레이저를 쏜 송신탑 번호를 계산하도록 하였다.

 

b_shoot에서 하나 pop한 후, 

a_shoot에 저장된 값의 높이가 pop된 높이보다 작다면, 해당 a_shoot 위에 있는 블록이 b_shoot에서 pop 된 송신탑을 때린다고 생각하면 된다.

 

따라서, hit = [0] * n 으로 선언된 곳에, hit[b_shoot에서 pop된 송신탑 번호 -1 ] 로 저장하면 된다.

만약, 작다면, break를 한 후, a_shoot에 하나의 새로운 블록을 추가하게 된다. (b_shoot에서 pop 된 블록)

 

이후, b_shoot에서 새로운 블록을 pop하여 위 과정을 반복한다.

 

또한, a_shoot에서는, 항상 h가 오름차순으로 쌓이게 된다.

따라서, 하나라도 새로운 높이가 맨 위 블록의 a_shoot이 큰 값을 가진다면 break를 할 수 있는 것이다.

즉, a_shoot의 밑 블록을 확인하지 않아도 만족하지 않을 것임을 알 수 있다. 

3. 코드

def laser(n):
    hit = [0] * n
    b_shoot = []
    temp_shoot = list(map(int, input().split()))
    for i in range(len(temp_shoot)):
        b_shoot.append([temp_shoot[i], i + 1])
    a_shoot = []
    while b_shoot:
        n_h, n_i = b_shoot.pop()

        while a_shoot:
            if n_h > a_shoot[-1][0]:
                o_h, o_i = a_shoot.pop()
                hit[o_i - 1] = n_i
            else:
                break

        a_shoot.append([n_h, n_i])

    return hit


if __name__ == "__main__":
    hit = laser(int(input()))
    print(" ".join(map(str, hit)))