프로그래머스 - 주식가격

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

Link

문제

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

제한사항

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

입출력 예

prices	return
[1, 2, 3, 2, 3]	[4, 3, 1, 1, 0]

풀이

Queue와 Stack 카테고리 문제.

먼저 Brute force로 접근해보자.

prices 요소의 각 자리에서 부터 시작해서 더 낮은 값이 얼마나 더 가서 나오는지를 카운트하고 그 값을 Answer에 append하면 된다.

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

이때의 Time complexity는 O(n^2)이고 Space complexity는 O(n)이다.

시간복잡도를 Linear하게 만들기 위해서는 어떻게 해야할까?

불필요한 반복을 줄여야하는데 위 코드를 자세히 보면 counting하는 부분이 불필요하게 반복되고 있다는 걸 알 수 있다.

매번 카운팅하는 것 보다 저장공간에 숫자와 그 숫자의 자리수 i를 같이 넣어주면서 그것보다 더 큰 값이 들어왔을 때 현재의 시간과 저장된 자리수 i를 비교한다면 카운팅할 필요가 없어진다.

이를 근거로 어떤 방법을 써야하는지 추론해본다면 결국 입력(추가) 순서와 처리 순서가 반대가 되므로 Stack을 쓰는 것이 맞다.

코드는 아래와 같다.

def solution(prices):
    answer = [0] * len(prices)
    stack = []
    for i in range(len(prices)):
        while stack and (prices[i] < stack[-1][1] or  i == len(prices) - 1):
                answer[stack[-1][0]] = i - stack[-1][0]
                stack.pop()
        stack.append([i, prices[i]])
    return answer

이때의 Time complexity는 O(2n) = O(n)이고 Space complexity는 O(2n) = O(n)이다.