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

문제 설명

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

제한사항

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

입출력 예

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

입출력 예 설명

• 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
• 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
• 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
• 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
• 5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.

처음에 무슨 말인지 이해를 못했었는데, 각 초의 변화량을 구체적으로 표현하면 다음과 같습니다.

• 1초 시점의 ₩1
  • [2, 3, 2, 3]와 비교하였을 때, 값이 떨어진 적이 없습니다.
• 2초 시점의 ₩2
  • [3, 2, 3]와 비교하였을 때, 값이 떨어진 적이 없습니다.
• 3초 시점의 ₩3
  • [2, 3]과 비교하였을 때, 1초 뒤(2)에 가격이 떨어집니다. 1초간 가격이 유지되었습니다.
• 4초 시점의 ₩2
  • [3]과 비교하였을 때, 값이 떨어진 적이 없습니다.
• 5초 시점의 ₩3
  • 비교할 숫자가 없기 때문에 0초간 가격이 떨어지지 않습니다.

위 내용을 종합하면 다음과 같은 풀이 방식을 세울 수 있습니다.

1. 문제에서 스택으로 동작하는 것은 시간값
2. prices == 0
   1. answer.append(0)
3. prices.pop(0) ≤ 남은 prices 배열의 모든 원소
   1. answer.append(len(남은 prices 배열 크기))
4. prices.pop(0) > 남은 prices 배열의 특정 원소
   1. answer.append(prices 배열의 특정 원소 순서 + 1)
   2. break

하지만 아래처럼 그대로 구현하게 된다면 prices.pop(0)과 배열의 모든 원소를 비교하는 과정에서 최대 O(n^2)의 시간 복잡도를 가지게 됩니다. 따라서 prices.pop(0)과 배열을 비교하는 과정을 하나의 과정으로 합쳐 O(n)으로 만들 수 있습니다.

def solution(prices):
    answer = []
    
    while True:
        tmp = prices.pop(0) 
        
        if (len(prices) == 0):
            answer.append(0)
            break
        
        answer.append(0)
        res = 0
        for i in range(len(prices)):
            if (tmp > prices[i]):
                answer[-1] = i+1
                break
            else:
                answer[-1] += 1
    
    return answer

위에서 작성한 예시에서 비교 과정 중 prices 배열을 중복해서 비교하는 것을 알 수 있습니다. 

반대로 생각하면 이전의 상태를 기억한 후 변하는 현재 상태(남은 prices 배열)과 비교하는 문제입니다.

또한 가격이 떨어지지 않은 기간을 계산하기 위해서는 그 가격이 prices 배열에서 어느 위치에 있었는지를 알아야만합니다. 그래서 배열의 인덱스를 스텍의 원소로 넣어야 합니다.

 

 

 

다른 테스트 케이스

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

def solution(prices):
    n = len(prices)
    answer = [0] * n
    stack = []
    
    for i in range(n):
        while stack and prices[stack[-1]] > prices[i]:
            tmp = stack.pop(-1)
            answer[tmp] = i - tmp
        stack.append(i)
    
    while stack:
        tmp = stack.pop(-1)
        answer[tmp] = n-1-tmp

    return answer

 

시간복잡도 약 O(n) 정도입니다...

 

어렵네요......

아무래도 문제집을 다 푼 이후에는 스택/큐 부분을 백준에서 더 많이 풀어봐야 할 것 같습니다.