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

https://school.programmers.co.kr/learn/courses/30/lessons/42584

프로그래머스

---

나의 풀이

초 단위로 기록된 주식 가격이 떨어지지 않은 기간이 몇 초인지 구하는 문제

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초간 가격이 떨어지지 않았습니다.

 

---

• prices에 아무것도 안남을 때까지 while문을 돌린다.
• 주식 가격을 하나씩 비교하며 문제를 해결한다.

효율성 실패~~~

def solution(prices):
    answer = []
    while prices:
        sec = 0
        stock = prices.pop(0)
        for p in prices:
            sec += 1
            if stock > p:
                break
        answer.append(sec)
    return answer

---

deque 라이브러리를 사용하여 문제를 해결해 보기로 함

구조는 똑같고 deque 라이브러리를 사용하니 성공했다.

평소에 list의 append, pop을 사용하여 구현하는데 앞으로 deque를 사용해야겠다.

from collections import deque

def solution(prices):
    answer = []
    prices = deque(prices)
    
    while prices:
        sec = 0
        stack = prices.popleft()
        for p in prices:
            sec += 1
            if stack > p:
                break
        answer.append(sec)
    return answer

---

다른 사람의 풀이

answer을 max값으로 초기화하고 빼가는 방법으로 결과를 구함

1. answer에 max값을 채운다.
2. stack에 현재 인덱스를 넣고 prices[i] 와 prices [i+1~n]까지 비교하여 값을 계산함

stock	1	2	3	2	3
j	0	1	2	3	4
i	1	2	3	4	5
return	4	3	3-2 =2	1	0

 

def solution(prices):
    length = len(prices)

    answer = [i for i in range(length - 1, -1, -1)]

    stack = [0]
    for i in range(1, length):
        while stack and prices[stack[-1]] > prices[i]:
            j = stack.pop()
            answer[j] = i - j
        stack.append(i)
    return answer