프로그래머스 Level 2 - 주식 가격

내 정답:

 

정말 가격해버리고 싶은 문제였다. 권장이 O(n)이라는데 내 얄팍한 지식으론 O(n)을 도저히 못맞추겠더라. 아래는 O(n^2)인 알고리즘이다.

def solution(prices):
    length = len(prices)
    answer = []
    for i in range(length):
        answer.append(length-i-1)
        for j in range(i+1, length):
            if prices[i] > prices[j]:
                answer.pop()
                answer.append(j-i)
                break
    return answer

 

다른 사람들의 정답:

 

딱히 O(n) 인 정답을 찾을 수 없었다. 어떻게 풀 수 있는지 좀 궁금하다.