😥 효율성을 높이기 위하여

• 가장 먼저 떠올랐던 풀이는 2차원 탐색이었다.
• 그렇게 하면 간단하게 풀 수 있지만 O(n^2)이 걸린다는 점이 마음에 걸렸다.
• 그래서 다른 아이디어를 많이 고민해보았지만, 떠오르지 않았다.
• 혹시나 하는 마음에 다른 사람들의 풀이도 보았지만, 모두 같았다.
• 더 고민하여 2차원 탐색을 돌리더라도 두 번 탐색하지 않기 위한 방법을 고안했다.
• dict 형을 이용하여 최근에 나온 값을 덮어씌우는 방법이다.
• 그러면 2차원 탐색을 하더라도 비용을 더 줄일 수 있을 것 같았다.
• 하지만 몇 줄 안되는 비교 코드가 더 많은 연산량을 잡아 먹은 것 같다.
• 오히려 효율성 부분을 하나도 통과하지 못했기 때문이다.

def solution(prices):
    answer = [0]
    data = {prices[-1]:-1}
    for index in range(-2, -len(prices)-1,-1):
        value = prices[index]
        for k, v in list(data.items())[::-1]:
            if value > k:
                answer.append(v - index)
                break
        else:
            answer.append(-1 - index)
        if data.get(value):
            del data[value]
        data[value] = index
    return answer[::-1]

😭 직관적이고 간단한 풀이

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