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

출처:: programmers.co.kr/learn/courses/30/lessons/42584?language=python3

분류:: 스택, 큐

 

1. 문제 이해 및 해결과정

  2. 인덱스를 이용 - BOJ 오큰수와 아이디어 비슷

 

 

2. 풀이방법

  1. [ python ] for문 ->  O(n^2)으로 n이 커지면 시간초과날 것임 

def solution(prices):
    n=len(prices) #초별 주식가격
    count=[] #결과배열
    for i in range(n):
        cnt=0
        for j in range(i+1,n):
            cnt+=1
            if prices[i]>prices[j]:
                break
            
        count.append(cnt)
    return count

  2. [ python ] 스택 ★

def solution(prices):
    n=len(prices)
    result=[0]*n #결과배열
    stack=[]
    
    for i in range(n):
        #result에는 자기보다 작은 수가 있을 경우 실행된다. ex) 1 2 (3 2) 3 => 3보다 작은 2가 있음 
        while stack and prices[stack[-1]]>prices[i]: 
            top=stack.pop()  
            result[top]=i-top #i:3, top:2 
        stack.append(i)         
        
    while stack:# 0 1 2 4 담겨있음 
        top=stack.pop()
        result[top]=n-1-top
        
    return result

 

 

3. 오답원인

 

4. 알게된 점