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

문제 확인

프로그래머스

---

나의 풀이

• 완전 탐색으로 풀면 시간 복잡도가 $O(N^2)$이기 때문에, 다른 방법으로 접근했다.
• 우선, 가격이 떨어지지 않는 경우를 가정해서 초기 [ic]answer[/ic]를 설정했다.
• 이후 가격이 떨어진다면, 현재 시간과 해당 prices 값이 입력된 시간 사이 차이를 계산해 answer 값을 수정해야 했다.
  • '어떻게 구하지?'라고 고민하다가 결국 다른 사람 풀이를 참고했다.

# 가격이 떨어지지 않은 기간
# '초기화 - 갱신'을 어떤 방식으로 할 지 고민
# [1] -> [1, 2] -> [1, 2, 3] -> [1, 2, 3, 2] -> [1, 2, 3, 2, 3]
# 새로 입력될 값이 stack의 마지막 보다 작은 경우 -> 그때 갱신

def solution(prices):
    # 초기 값 입력
    # 한번도 떨어지지 않을 때 가정
    plus_time = [i for i in range(len(prices) - 1, -1, -1)]
    # N초 정보
    time = []
    for i, price in enumerate(prices):
        # 가격이 떨어진 경우 처리
        # 이전 시간의 정보를 확인 함
        while time and prices[time[-1]] > price:
            j = time.pop()
            plus_time[j] = i - j
        # 현재 시간 정보 저장
        time.append(i)
    return plus_time

---

참고

Programmers | 주식가격 - Python