[프로그래머스/Python] 주식가격(스택)

코딩테스트 연습 - 주식가격

 

1. 이중 for문

 

현시점 이후의 가격을 다 살펴봐야 되므로 O(n^2)의 효율성을 보인다. 

 

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

 

2. Stack 이용

 

사실상 이후의 모든 시간을 볼 필요가 없다. 계속 값이 오를 때는 그 시점들을 다 스택에 넣다가 값이 떨어지는 그 시점에서 떨어진 값보다 큰 애들을 다 빼주면서 시간을 기록하면 된다. 이렇게 구현을 할 시 for문을 한번만 돌게 되므로 시간 복잡도가 O(n)으로 감소한다.

 

1) 시간과 값을 동시에 넣을 때

 

def solution(prices):
    answer = [0]*len(prices)
    stack = []
    for time, item in enumerate(prices):
        while stack and stack[-1][1] > item:
            v = stack.pop()
            answer[v[0]] = time- v[0] 
        
        stack.append([time, item])
    
    # 끝까지 가격이 떨어지지 않은 애들
    while stack:
        time = stack.pop()[0]
        answer[time] = len(prices)-1 - time
        
    return answer

 

2) 시간만 넣어도 된다.

 

def solution(prices):
    answer = [0]*len(prices)
    
    s = []
    for i, p in enumerate(prices):
        while s and prices[s[-1]] > p:
            j = s.pop()
            answer[j] = i-j            
        s.append(i)
    
    while s:
        i = s.pop()
        answer[i] = len(prices)-1-i
    
    return answer