BOJ [탑]

문제

문제보기

2022-03-23

서로 높이가 다른 탑의 꼭대기에서 왼쪽으로 레이저를 쏠 때 레이저는 탑에 부딪히면

멈춘다. 각 레이저가 멈추는 위치를 구하라는 문제이다.

출처:https://mygumi.tistory.com/101

풀이

아 이거 좀 생각해봤으면 좋았을 텐데 걍 답을 봤다.

앞에서 부터 탐색한다 생각해보자. 1번탑보다 2번탑이크면 이제 1번탑은 고려할 필요가없다.

왜냐면 1번탑에서 막힐 레이저는 2번탑에서 걸러지기 때문이다.

1번탑이 2번탑보다 크면 1,2번 둘다 고려해야 한다. {2번보다 작은애들}, {1,2번 사이}, {1번보다 큰 애들} 다 결과가 달라지기 때문이다.

따라서 앞에부터 탐색하면서 지울애들 지우고 뒤로 넘긴다.

그러면 메모리와 시간을 모두 줄일 수 있다.

코드

n = int(input())
top = list(map(int,input().split()))
stk = []
get_top = [0 for _ in range(len(top))]
for i in range(len(top)):
    
    while stk:
        
        if stk[-1][0] > top[i]:
            get_top[i] = stk[-1][1]+1
            break
        else:
            stk.pop()
    stk.append([top[i],i])

for i in get_top:
    print(i,end=" ")