반응형
https://school.programmers.co.kr/learn/courses/30/lessons/42584
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제풀이
단조 증가 스택을 이용하는게 핵심이다.
- 조건에 해당하지 않는 인덱스를 스택에 저장.
- 조건에 해당한다면 현재 인덱스 - 스택 인덱스 값은 answer[stack] 인덱스에 대한 결과가 된다.
- 조건에 해당하지 않았던 인덱스들은 따로 처리하며 배열의 길이 - 1 - 스택 인덱스 값은 answer[stack] 인덱스에 대한 결과가 된다.
from collections import deque
def solution(prices):
n = len(prices)
answer = [0] * n
stack = deque()
for i in range(n):
while stack and prices[i] < prices[stack[-1]]:
idx = stack.pop()
answer[idx] = i - idx
stack.append(i)
while stack:
idx = stack.pop()
answer[idx] = n - 1 - idx
return answer
