Lv 2 주식가격

 

문제 설명

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

제한사항

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

문제 풀이

문제를 이해를 잘 못해서 너무 오래 시간을 끌었다.

문제에서 원하는건, 언제 시점부터 가격이 떨어지냐 이다. 

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

위 표를 보면, 1의 경우 숫자가 떨어지지 않으니까 4초 동안 유지 됐다. 2의 경우도 숫자가 떨어지지 않았으니 3초동안 유지 됐다.

3의 경우 1초 후에 2로 숫자가 떨어진다. 아까도 말했지만, 문제에서 원하는건 언제 떨어졌냐다. 그 다음 2는 수가 떨어지지 않았으니 1초. 3은 마지막 숫자이니 0 으로 마무리가 된다.

 

이해가 잘 안갈수도 있겠지만, 문제의 핵심은 떨어지는 그 순간을 원하는 거다

 

코드

from collections import deque

def solution(prices):
    answer = []
    prices = deque(prices)
    t = len(prices)
    while t != 0:
        cnt = 0
        tmp = prices.popleft()
        for i in prices:
            cnt += 1
            if tmp > i :
                break
        answer.append(cnt)
        t -= 1
    
    return answer

처음에 deque를 사용하지 않고 그냥 리스트의 pop을 이용했었다. 그런데 pop의 경우 시간 복잡도가 O(n) 이라서 효율성에서 계속 빠꾸가 났다. 그래서 열심히 서칭을 한 결과 deque로 사용하여 popleft()를 이용하면 시간 복잡도가 줄어드는 것을 볼 수 있었다.