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

🗃️문제 설명

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

🖥️코드

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

👉겉으로는 2중 for문을 사용하고 있어 시간 복잡도가 O(N^2)이나 초 단위로 기록된 주식가격이 하락세를 보이는 시점에 break문을 걸기 때문에 실질적으로는 O(N^2)보다 적게 나온다.

🖥️코드

def solution(prices):
    stack = []
    answer = [i for i in range(len(prices)-1, -1, -1)]
    for i in range(len(prices)):
        while stack and prices[stack[-1]] > prices[i]:
            prev = stack.pop()
            answer[prev] = i - prev
        stack.append(i)
    return answer

🔒문제 출처

프로그래머스 - 주식 가격