[Leetcode/Python] 901. Online Stock Span

문제 링크

Online Stock Span - LeetCode

문제 설명

 일부 주식에 대한 일일 가격 시세를 수집하고 해당 주식의 현재 가격 범위를 반환하는 알고리즘을 설계합니다.

 오늘 주식 가격의 범위는 주식 가격이 오늘 가격보다 낮거나 같은 연속 일수(오늘부터 시작하여 뒤로)로 정의됩니다. 예를 들어 다음 7일 동안의 주식 가격이 [100,80,60,70,60,75,85]인 경우 주식 범위는 [1,1,1,2,1,4, 6].

StockSpanner 클래스를 다음과 같이 구현합니다.
  - StockSpanner() : 클래스의 개체를 초기화합니다.
  - int next(int price) : 오늘의 가격이 price 인 경우 주식 가격의 범위를 반환합니다.

 처음에는 간단히 마지막에 넣은 price보다 낮거나 같은 가격의 주식이 몇개 존재하는지 세는 줄 알았습니다. 예를 들어서 4번째인 70이 들어올 때는 60, 70이 두개이므로 2를 출력하면 되는 걸로 생각했습니다.

 

 하지만 문제를 자세히 읽어보면 마지막 가격을 기준으로 낮거나 같은 경우의 연속일 수를 구해야 합니다. 예를 들어 [10, 30, 20]이 들어온다면 [1, 2, 2]가 아닌 [1, 2, 1]을 반환해야 합니다.

 

입출력 예시

price	return
100	1
80	1
60	1
70	2
60	1
75	4
85	6

 

제한 사항

• 1 <= price <= 105
• 최대 10^4 개의 호출이 다음에 만들어 질 수 있습니다.

 

문제 풀이

 처음에는 문제를 잘못 이해해서 투 포인터로 풀었습니다. 그러나 [10, 30, 20]이 입력되었을 때 다른 내용인걸 눈치채서 풀이를 변경했습니다.

 

 그래서 정렬을 하지않고 마지막에 값을 추가하는 스택 형식으로 만들었습니다. 만약 [100, 80, 60, 70]이 들어있다면, 마지막에 80이 들어오면 뒤에서 3개까지만 갯수를 세면 됩니다. 그리고 마지막에 80을 추가하고 4를 리턴하면 문제가 풀립다.

 

 이 경우 시간복잡도와 공간복잡도는 O(n)입니다. 그러나 풀이법을 봤을 때는 monotone stack을 응용하는 것으로 나왔습니다. monotone stack, 모노톤 스택이라 불리는 이것은 오름차순이나 내림차 순으로 완만하게 쌓는 스택을 말합니다.

 

 내림차순으로 설정한 모노톤 스택을 예로 들어봅시다. [10, 7, 6] 이 들어있는 스택에 8을 추가하면 맨 끝에 두 숫자를 빼고 [10, 8]이 됩니다. 이 모노톤 스택의 원리를 이용하여 문제를 풀었습니다.

 

 해당 문제는 모노톤 스택안에 [price, 연속일 수] 를 넣어 문제를 풀었습니다. 예를 들어, 위의 [100, 80, 60, 70]을 모노톤 스택으로 변경할 경우 다음과 같이 넣어집니다.

 

  [ [100, 1], [80, 1], [70, 2] ]

 

 60의 경우는 내림차에서 사라지고, [70, 2]가 생겨나죠. 만약 여기서 80이 들어오면 어떻게 바뀔까요?

 

 [ [100, 1], [80, 4] ]

 

 마지막의 두 숫자 80, 70이 없어지고, 각 연속일수 1과 2를 더하여 총 4의 연속일 수가 생겨납니다. 이어서 다음의 과정을 봅시다.

 

• 90을 넣을 경우 : [ [100, 1], [90, 5] ] => 리턴값 5
• 다음으로 100 을 넣을 경우 : [ [100, 7] ] => 리턴값 7
• 다음으로 90을 넣을 경우 : [ [100, 7], [90, 1] ] => 리턴값 1

 

 이 경우 공간복잡도는 O(n)이지만, 시간복잡도의 경우 O(1)수준까지 줄어들게 됩니다. 이 문제에서는 모노톤 스택이라는 새로운 개념을 알아낸 것만으로도 큰 지식을 얻은 셈입니다.

 

소스코드

class StockSpanner:

    def __init__(self):
        self.stocks = []

    def next(self, price: int) -> int:
        count = 1
        while self.stocks and self.stocks[-1][0] <= price:
            count += self.stocks.pop()[1]
        self.stocks.append([price, count])
        return count

 

 

코딩 테스트, 어떻게 대비해야 할까?