[알고리즘]주식가격(프로그래머스 문제) python 풀이(스택)

주식가격 문제

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

 

 

이 문제는 prices 리스트 각각의 값들이 몇초 동안 가격이 안떨어지고 있었는지 return 해주면 되는 문제 이다.

return 은 prices의 리스트의 개수만큼 이므로 for문으로 풀 경우 0으로 초기화 해주면 쉽게 풀수 있다. 

 

[풀이] 1. Brute force

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

파이썬은 answer = [0] * 개수 하면 개수만큼 0으로 초기화된 리스트가 만들어 진다.

이 문제가 스택이나 큐로 푸는 문제인걸 봤을때 스택이나 큐로 풀었을때 시간 효율성이 많이 좋아질 것이다.

 

스택으로 푸는 방법은 처음 price를 stack에 쌓고 다음 price가 더 크면 스택에 쌓고 작으면 pop을 한다. 

 

 

[풀이] 2. Stack

def solution(prices):
    answer = [0]*len(prices)
    stack = []
 
    for i, price in enumerate(prices):
        #stack이 비었이면 false
        while stack and price < prices[stack[-1]]:
            j = stack.pop()
            answer[j] = i - j
        stack.append(i)
 
    # for문 다 돌고 Stack에 남아있는 값들 pop
    while stack:
        j = stack.pop()
        answer[j] = len(prices) - 1 - j
 
    return answer

Brute force는 시간이 100~200ms 였지만 스택을 이용하니 시간이 50ms 아래로 떨어졌다. 스택을 이용하니 시간 효율성이 좋아진걸 확인할 수 있었다.