2493. 탑

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

 

✔ 유형 : 스택

✔ 문제 풀이: 반복문으로 검사하면 최악의 경우 O(N^2)의 시간복잡도가 나온다. 이를 해결하기 위해 stack을 이용한다.

 

구해야 하는 답: 각 탑에서 발사한 레이저 신호를 수신한 탑의 번호 리스트.

 

 

코드

import sys
input=sys.stdin.readline # input함수 바꾸기

# input
N = int(input())
towers = list(map(int,input().split())) #list 자료구조지만 스택 사용 가능


stack = list()
answer = [0 for i in range(N)]

# 2. 
for i in range(N):
    # 1. 현재 스택에 값이 존재한다면?
    while(stack):
        if stack[-1][1] > towers[i]:
            answer[i]= stack[-1][0] + 1 
            break
        else:
            stack.pop()
            
    stack.append([i, towers[i]])
    
print(*answer)