[Programmers] 주식 가격

문제

---

문제 링크

 

풀이

---

두 가지 풀이 방식을 소개해 보겠습니다.

첫 번째 풀이는 흔히 생각할 수 있는 완전탐색으로 O(N²)의 풀이이고,

두 번째 풀이는 단조 스택을 이용한 효율적인 풀이입니다.

풀이 1

현재(i)원소를 기준으로 남은 원소들(j)를 탐색하며 모두 비교한다.

완전 탐색을 사용한 풀이이므로 아이디어는 생략하겠습니다.

알고리즘 설명

순서는 다음과 같습니다.

1. 모든 주식들이 떨어지지 않는다고 가정하에 ans 배열을 최대 날짜들로 초기화한다.
2. price의 각 원소들을 비교하며 떨어진 날이 있을 경우에만 ans값을 업데이트한다.

 

구현 코드

[python]

def solution(price):
    ans = [len(price) - i - 1 for i in range(len(price))]
    for i in range(len(price)):
        cur = price[i]
        
        for j in range(i + 1, len(price)):
            if (price[j] < cur):
                ans[i] = j - i
                break

    return ans

 

풀이 2

모노토닉 스택을 활용

아이디어

이 아이디어는 단조 스택(Monotonic Stack) 개념을 활용하는 대표적인 예시입니다.

문제를 이해하며 시뮬레이션해보면 결국 자신보다 작은 최초 수를 찾는 문제임을 파악할 수 있고, 이는 단조 스택을 제대로 공부했다면 이를 떠올릴 수 있습니다.

 

알고리즘

• ans: 각 가격이 떨어지지 않은 기간을 저장하는 배열
• stack: price 인덱스를 저장하는 스택

1. 가격 배열 순회:
   • prices 배열을 순회하면서 각 가격을 처리한다.
   • 현재 가격이 스택의 top에 있는 가격보다 낮다면, 가격이 떨어진 것으로 판단하고 해당 인덱스를 처리한다.
2. 가격이 떨어지는 시점 계산:
   • 스택에서 해당 인덱스를 팝하여 가격이 떨어진 시점을 계산하고, ans 배열에 저장헌다.
   • 떨어진 가격이 나올 때마다 반복한다.

 

구현 코드

[pytjon]

def solution(prices):
    # 1. 초기화
    # ans = [4, 3, 2, 1, 0]
    # sta: 가격의 인덱스를 저장하는 스택택
    ans = [len(prices) - 1 - i for i in range(len(prices))]
    sta = []

    # 2. 가격 배열 순회

    for i in range(len(prices)):
        while sta and prices[sta[-1]] > prices[i]:
            idx = sta.pop()
            ans[idx] = i - idx

        sta.append(i)

    return ans