100일 동안 매일 알고리즘을 하면? - 11일차

https://programmers.co.kr/learn/courses/30/lessons/42584

코딩테스트 연습 - 주식가격

수학으로 풀었다. 

약간 수학적 귀납법, DP 느낌으로 푼것같은데 이게 직관적인 풀이는 아닌것같긴하다. 다른 사람들의 코드를 보니깐 다 고만고만한데, 다들 시간복잡도 O(N^2) 으로 풀었다. 내 코드 또한 O(N^2) 이긴한데 break 문 덕분에 시간초과가 안난듯하다.

def solution(prices):
    ret = [0] * len(prices);
    
    for i in range(len(prices) - 1):
        if prices[i] <= prices[i + 1]:
            continue;
        elif prices[i] > prices[i + 1]:
            ret[i] = 1;
            if (i > 1):
                for j in range(i - 1, -1, -1):
                    if prices[j] > prices[i + 1]:
                        if ret[j] == 0:
                            ret[j] = (i + 1 - j);
                            continue;
                    else:
                        break;
    for i,v in enumerate(ret):
        if v == 0:
            ret[i] = len(ret) - 1 - i;
            
    return ret