[프로그래머스 주식 가격] 파이썬 풀이

• [프로그래머스 주식 가격] 파이썬 풀이
  • 문제
  • Keypoints
  • Solution
  • References

[프로그래머스 주식 가격] 파이썬 풀이

문제

시간별 주식 가격이 주어질 때, 각 가격이 언제 떨이지는 지 찾는 문제.

효율성 검증이 있으므로, for문 2개를 단순하게 돌릴 경우, 통과하지 못한다. 

Keypoints

• List Traversal 문제이다.
• 리스트의 원소에 대해서 해당 원소 이후로 값이 감소한 곳을 빠르게 찾아야 한다.
• 뒤에서부터 최소값의 인덱스를 가지고 있다면, Search 해야 하는 범위가 줄어든다. [효율성]

Solution

def solution(prices):
    N = len(prices)
    answer= [0 for i in range(N)]
    min_index = N-1
    for i in range(N-2, -1, -1): # Reverse traversal
        if prices[i] > prices[min_index]: # current value will drop in the future
            for j in range(i+1, min_index+1): # find only possible positions
                if prices[i] > prices[j]:
                    answer[i] = j - i
                    break 
        elif prices[i] < prices[min_index]:
            min_index=i
            answer[i] = N-i-1
        else:
            answer[i] = N-i-1


    return answer

References

Problem Link