주식가격

문제 접근

prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
이므로 O(n)를 구현해야하는 문제입니다.

각각의 리스트 요소가 n, n-1, n-2, ... 방식으로 비교하는 경우이므로 스택을 통해 해결하면 시간복잡도를 맞출 수 있을 것 같습니다.

문제풀이

def solution(prices):
    stack = []
    dic = {}
    for i in range(len(prices)):
        dic[i] = 0
    for idx, price in enumerate(prices):
        if len(stack) == 0:
            stack.append({'idx': idx, 'price': price})
        else:
            if stack[len(stack) - 1]['price'] <= price:
                stack.append({'idx': idx, 'price': price})
            else:
                while len(stack) != 0 and stack[len(stack) - 1]['price'] > price:
                    dic[stack[len(stack) - 1]['idx']] = idx - stack[len(stack) - 1]['idx']
                    stack.pop()
                stack.append({'idx': idx, 'price': price})
    if len(stack) > 0:
        for price_obj in stack:
            dic[price_obj['idx']] = stack[len(stack) - 1]['idx'] - price_obj['idx']
    answer = [dic[key] for key in dic]
    return answer

느낀 점

이상하게도 O(n^2)를 사용한 사람들보다 속도가 느린 것 같습니다. 효율성 테스트는 통과했지만, 이유를 생각해봐야 할 것 같습니다.