[프로그래머스/스택과큐] 주식가격

https://school.programmers.co.kr/learn/courses/30/lessons/42583

프로그래머스

 

📌 문제 

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

제한사항

• prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
• prices의 길이는 2 이상 100,000 이하입니다.

📌 풀이 

아이디어가 생각이 안나서 완전탐색 방식으로 한 원소마다 순서대로 언제 가격이 하락하는지 count하는 코드 작성 

⇒ 시간초과 발생 

⇒ 다른 사람들의 아이디어 참조 

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

def solution(prices):
    
    answer = [0] * len(prices)
    stack = [] 
    
    for idx , price in enumerate(prices) :
        
        while stack and price < prices[stack[-1]] :
            last = stack.pop() 
            answer[last] = idx - last
        
        stack.append(idx)
        
        if answer[idx] == 0 :
            answer[idx] = len(prices) - idx -1
        
    return answer