[Python/파이썬] 프로그래머스 주식가격

프로그래머스

코드

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

코드는 따로 설명할 필요도 없이 간단하다.

주식 가격이 떨어지는 시점까지 for문을 돌며 answer[i]를 1씩 증가시켜준다. 그러기 위해 answer 배열은 미리 모두 0으로 초기화시켜놓았다.

 

근데 아무리 봐도 이 코드는 내가 작성하면서 생각해봐도 효율성이 별로인거 같아서 제출하고 나서 다른 사람들은 어떻게 풀었는지 보았다. 동일한 방식의 풀이가 많긴 했는데 보다보니 스택을 이용하여 푼 풀이가 눈에 들어왔다.

def solution(prices):
    stack = []
    answer = [0] * len(prices)
    for i in range(len(prices)):
        if stack:
            while stack and stack[-1][1] > prices[i]:
                past, _ = stack.pop()
                answer[past] = i - past
        stack.append([i, prices[i]])
    for i, s in stack:
        answer[i] = len(prices) - 1 - i
    return answer

코드를 보고 내가 이해한 내용을 설명하자면 우선 이 코드는 스택을 이용한 풀이이다.

만약 중간에 가격이 떨어진다면 현재 보고 있는 가격보다 낮은 가격이 나올 때까지 answer[past]에 가격이 떨어지지 않은 기간인 i-past 값을 저장해준다.

스택에 남은 값들은 끝까지 가격이 떨어지지 않은 것이므로 prices 배열의 전체 길이에서 (i+1)을 빼주면 된다.

 

위의 코드는 시간복잡도가 O(N^2)인데 아래의 스택을 이용한 코드는 O(N)이라 효율성면에서 더 좋은 코드였다.