주식가격 : level2_파이썬

문제

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

내가 푼 풀이

def solution(prices):
    answer = [0 for i in range(len(prices))]
    
    i = 0
    while 1:
        now = prices[i]

        for j in range(i+1, len(prices)):
            if prices[j] < now:
                answer[i] = j - i
                break
            else:
                answer[i] += 1
        i += 1

        if i == len(prices) - 1:
            answer[i] = 0
            break

    return answer

✔ 제출하면서 시간 초과가 뜰지 알았는데 통과돼서 행복했다..하지만 뭔가 찝찝한 기분 좋음인걸...문제 유형으로 적힌 스택이나 큐를 사용하지 않아서 그런 것 같다..ㅋㅋㅋㅋㅋ
근데 좋아요가 많았던 풀이도 나와 비슷한 풀이였다..하지만 역시 입력크기가 커질 경우 효율적이지 않은 풀이같다ㅠ

스택을 이용한 풀이

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

    for i in range(len(prices)):
        if stack != []:
            while stack != [] and stack[-1][1] > prices[i]:
                past, _ = stack.pop()
                answer[past] = i - past
        stack.append([i, prices[i]])

    for i, s in stack:  
        answer[i] = len(prices) - 1 - i

    return answer

처음에 나도 스택을 이용해서 풀려고 했었다. 근데 나는 스택에 오직 price만 삽입하는 방식으로 생각했는데 그러면 이미 가격이 떨어져서 처리할 필요가 없는 원소들을 어떻게 처리해야 할지가 해결되지 않았다.
🔑 위 풀이처럼 stack에 인덱스와 price를 함께 넣어서 처리하면 해결되었다.

stack에 인덱스도 함께 넣는 방식!