[LeetCode] 901. Online Stock Span

LeetCode 901. Online Stock Span
🗓️ Daily LeetCoding Challenge November, Day 9
Stack Binary Search

https://leetcode.com/problems/online-stock-span/

Online Stock Span - LeetCode

1. 문제 설명

특정 주식에 대한 일일 가격을 수집하고, 주가폭을 계산하는 문제이다.

오늘 주가폭은 오늘 주가보다 작거나 같은 최대 연속 일수로 정의한다.

따라서 스택에 오늘의 가격과 연속일수를 함께 저장하고, 이를 잘(?) pop해서 오늘의 주가폭을 리턴하면 된다.

 

아래와 같이 7일간 주식의 가격이 주어진다고 가정하자.

[[], [100], [80], [60], [70], [60], [75], [85]]

처음 []는 StockSpanner()의 initialization같으니 가볍게 무시하고 그 다음부터 생각하면 된다.

100은 처음 들어온 int값이므로 연속 1일 주가가 작거나 같다. 따라서 1을 리턴한다.

80은 100보다 작은 값이므로 연속 1일 주가가 작거나 같다. 따라서 1을 리턴한다.

60은 80보다 작은 값이므로 연속 1일 주가가 작거나 같다.따라서 1을 리턴한다.

70은 60보다 크고, 80보다 작은 값이므로 연속 2일 70(=현재 price)보다 주가가 작거나 같다. 따라서 2를 리턴한다.

이러한 방식으로 결과값을 계속 리턴하면 된다.

 

처음에 문제를 잘못 읽고 오늘 주가보다 작거나 같은 모든 일수를 출력했다가 WA를 받았다. 문제를 잘 읽자

그래서 처음에 binary search를 이용하여 현재 price의 인덱스를 찾고 리턴했었다.

해석을 잘못 했으니 맞을 리가 없지..

---

2. 문제 접근

스택에 넣을 때 현재 가격과 최대 연속 일수를 함께 넣어주면 된다.

최대 연속 일수를 res에 할당했을 때, price가 스택의 마지막 price보다 크거나 같으면 계속 pop한다.

이때 해당 price의 최대 연속 일수를 res에 더한 값이 우리가 원하는 최대 연속 일수이고, 이를 리턴한다.

물론 리턴 전에 [price, res]를 스택에 넣는 것을 잊지 말자.

그래야 다음 주식의 price가 들어왔을 때 제대로 된 최대 연속 일수를 구할 수 있으니까 :)

---

3. 구현 코드

class StockSpanner:

    def __init__(self):
        self.stack = [[0, 0]]

    def next(self, price: int) -> int:
        print(self.stack)
        res = 1
        while self.stack and price >= self.stack[-1][0]:
            res += self.stack.pop()[1]  # 현재 price가 stack의 마지막 값보다 크거나 같으면
                                        # 계속 pop하면서 최대 연속 일수를 계산한다.
        self.stack.append([price, res])

        return res

스택에서 list 형태로 pop한 이후 인덱싱을 통해 res를 바로 계산할 수 있다는 것을 깨달았다. (잡기술 += 1)