2493_탑

입력

첫 번째 줄에 리스트의 길이를 입력
두 번째 줄에 리스트의 요소들을 입력

출력

입력받은 리스트에서 각 요소들의 왼쪽 방향으로 값이 더 큰 가장 가까운 인덱스를 출력

조건

• N의 크기는 최대 500,000, 제한 시간 1.5초 => 시간복잡도 O(N) 요구
• 조건에 만족하는 값이 없다면 0으로 설정

풀이

2개의 스택을 설정하여 현재 고려하는 값보다 작은 모든 오른쪽의 값들을 설정하는 풀이

1. 입력 stack과 참조 stack 설정

N = int(input())
top_list = deque(map(int, sys.stdin.readline().split()))
ans = [0]*N
stack = deque([])

2. 입력 stack에 있는 요소들을 모두 확인할 때까지 반복
   입력 stack의 가장 오른쪽에 있는 값을 curr로 설정
   --참조 stack의 top = curr 값 기준으로 오른쪽 방향에서의 가장 가까운 값
   참조 stack의 top <= curr 조건을 만족하면 ans[top_index] = curr_index로 설정
   참조 stack의 top < curr ===> break (참조 stack의 top밑에 있는 요소들은 top보다 다 큰 값이기 때문에 밑의 값들을 비교할 필요가 없음)
   curr값을 참조 stack에 push

while top_list:
    curr = top_list.pop()
    N -= 1
    
    while stack:
        tmp = stack.pop()
        if tmp[0] <= curr: ans[tmp[1]] = N+1
        else:
            stack.append(tmp)
            break
    
    stack.append([curr, N])

전체 코드

탑