[프로그래머스] 42584. 주식가격

Programmers - 42584. 주식가격

접근1

맘같아선 싹 다 리스트에 박아버리고 for문 돌리고 싶다.

한번 해볼까

def solution(prices):
    answer = [0]*len(prices)

    for i in range(len(prices)):
        for j in range(i):
            if answer[j] == 0:
                if prices[j] > prices[i]:
                    answer[j] = i-j

    for i in range(len(answer) - 1):
        if answer[i] == 0:
            answer[i] = len(answer) - 1 - i
            
    return answer

 

네 당연히 잘 돌아가구요

존나 오래 걸립니다

 

접근2

from collections import deque
def solution(prices):
    answer = [0]*len(prices)

    deq = deque(prices)

    for i in range(len(prices)-1, -1, -1):
        popPrice = deq.pop()
        for j in range(i):
            if popPrice < prices[j]:
                answer[j] = i-j

    leng = len(answer)
    for i in range(leng-1):
        if answer[i] == 0:
            answer[i] = leng - 1 - i

            
    return answer

똑같은 알고리즘으로 될 거라고 생각한 내가 병신임

 

접근3

그런데 이제 개선을 곁들인

def solution(prices):
    answer = [0]*len(prices)
    leng = len(prices)

    for i in range(leng):
        for j in range(i+1, leng):
            if prices[i] > prices[j]:
                answer[i] = j - i
                break
        if answer[i] == 0:
            answer[i] = leng-1 - i

    return answer

필요 없는 반복계산을

숭덩숭덩 잘라내니까

해결이 됐어요 와!