LeetCode/LeetCode75

[LeetCode 75] Medium - 901. Online Stock Span

hyunkookim 2024. 11. 10. 17:33

901. Online Stock Span

 

Design an algorithm that collects daily price quotes for some stock and returns the span of that stock's price for the current day.

The span of the stock's price in one day is the maximum number of consecutive days (starting from that day and going backward) for which the stock price was less than or equal to the price of that day.

  • For example, if the prices of the stock in the last four days is [7,2,1,2] and the price of the stock today is 2, then the span of today is 4 because starting from today, the price of the stock was less than or equal 2 for 4 consecutive days.
  • Also, if the prices of the stock in the last four days is [7,34,1,2] and the price of the stock today is 8, then the span of today is 3 because starting from today, the price of the stock was less than or equal 8 for 3 consecutive days.

Implement the StockSpanner class:

  • StockSpanner() Initializes the object of the class.
  • int next(int price) Returns the span of the stock's price given that today's price is price.

 

Example 1:

Input
["StockSpanner", "next", "next", "next", "next", "next", "next", "next"]
[[], [100], [80], [60], [70], [60], [75], [85]]
Output
[null, 1, 1, 1, 2, 1, 4, 6]

Explanation
StockSpanner stockSpanner = new StockSpanner();
stockSpanner.next(100); // return 1
stockSpanner.next(80);  // return 1
stockSpanner.next(60);  // return 1
stockSpanner.next(70);  // return 2
stockSpanner.next(60);  // return 1
stockSpanner.next(75);  // return 4, because the last 4 prices (including today's price of 75) were less than or equal to today's price.
stockSpanner.next(85);  // return 6

 

Constraints:

  • 1 <= price <= 10^5
  • At most 10^4 calls will be made to next.

 

문제 풀이

 

주식 스팬 문제는 매일 주식 가격이 주어질 때, 그날을 포함해 **뒤로 연속된 날 중 오늘의 가격보다 작거나 같은 날의 수(스팬)**를 계산하는 문제입니다.

스팬의 정의

  • 스팬(Span): 오늘의 가격을 포함하여 오늘의 가격보다 작거나 같은 연속된 날의 수.
  • 따라서, 자기 자신도 항상 포함됩니다.
    • 최소 스팬 값은 항상 1입니다.
    • 예: 첫날 주식 가격이 100이면, 스팬은 1입니다. (이전 데이터가 없어도 자기 자신만 포함)

 

주요 질문과 답변

  1. 오늘의 가격도 포함되나요?
    • 네, 스팬의 정의에 따라 자기 자신도 포함됩니다.
    • 오늘만 포함되어도 최소 스팬 값은 항상 1입니다.
  2. 70이 들어왔을 때, 왜 스팬이 2인가요?
    • 현재까지의 가격: [100, 80, 60].
    • 오늘 가격 70보다 작거나 같은 이전 연속된 날의 가격: [70, 60].
    • 따라서 스팬은 2.
  3. 왜 next(100)에서 1이 반환되나요?
    • 오늘이 첫날이므로 이전 가격 데이터가 없습니다.
    • 하지만 오늘의 가격은 항상 포함되므로 스팬은 1입니다.

문제 해결 방법

이 문제는 **Monotonic Stack(단조 스택)**을 사용하면 효율적으로 해결할 수 있습니다.

알고리즘:

  1. 스택에 [가격, 스팬] 쌍을 저장합니다.
  2. 새로운 가격이 들어올 때:
    • 스택의 맨 위 값이 현재 가격보다 작거나 같으면 스택에서 제거하며 스팬을 누적합니다.
  3. 계산된 스팬과 현재 가격을 스택에 추가합니다.
  4. 최종적으로 스팬 값을 반환합니다.
class StockSpanner:
    def __init__(self):
        # 스택 초기화: [가격, 스팬] 쌍을 저장
        # 스택에는 "현재 가격보다 큰 값"만 유지하여 효율적으로 연속된 스팬 계산
        self.stack = []

    def next(self, price: int) -> int:
        # 현재 날의 스팬을 최소 1로 초기화 (자기 자신 포함)
        span = 1

        # 스택의 맨 위 값이 현재 가격보다 작거나 같으면 스택에서 제거
        # 제거하면서 스팬을 누적
        while self.stack and self.stack[-1][0] <= price:
            stack_price, stack_span = self.stack.pop()
            span += stack_span  # 제거된 값의 스팬을 현재 스팬에 더함

        # 현재 가격과 계산된 스팬을 스택에 추가
        self.stack.append((price, span))

        # 현재 날의 스팬 반환
        return span

# 시뮬레이션 예제
"""
입력:
["StockSpanner", "next", "next", "next", "next", "next", "next", "next"]
[[], [100], [80], [60], [70], [60], [75], [85]]

출력:
[null, 1, 1, 1, 2, 1, 4, 6]

시뮬레이션 과정:
"""

# Step 1: StockSpanner 객체 생성
stockSpanner = StockSpanner()  # 스택 초기화: []

# Step 2: next(100)
"""
현재 가격: 100
스택 비어 있음 → 스택에 (100, 1) 추가
스팬 = 1
스택 상태: [(100, 1)]
"""
print(stockSpanner.next(100))  # 출력: 1

# Step 3: next(80)
"""
현재 가격: 80
80 <= 100 → 스택 유지
스택에 (80, 1) 추가
스팬 = 1
스택 상태: [(100, 1), (80, 1)]
"""
print(stockSpanner.next(80))  # 출력: 1

# Step 4: next(60)
"""
현재 가격: 60
60 <= 80 → 스택 유지
스택에 (60, 1) 추가
스팬 = 1
스택 상태: [(100, 1), (80, 1), (60, 1)]
"""
print(stockSpanner.next(60))  # 출력: 1

# Step 5: next(70)
"""
현재 가격: 70
70 > 60 → 스택에서 (60, 1) 제거, 스팬 += 1
스택에 (70, 2) 추가
스팬 = 2
스택 상태: [(100, 1), (80, 1), (70, 2)]
"""
print(stockSpanner.next(70))  # 출력: 2

# Step 6: next(60)
"""
현재 가격: 60
60 <= 70 → 스택 유지
스택에 (60, 1) 추가
스팬 = 1
스택 상태: [(100, 1), (80, 1), (70, 2), (60, 1)]
"""
print(stockSpanner.next(60))  # 출력: 1

# Step 7: next(75)
"""
현재 가격: 75
75 > 60 → 스택에서 (60, 1) 제거, 스팬 += 1
75 > 70 → 스택에서 (70, 2) 제거, 스팬 += 2
스택에 (75, 4) 추가
스팬 = 4
스택 상태: [(100, 1), (80, 1), (75, 4)]
"""
print(stockSpanner.next(75))  # 출력: 4

# Step 8: next(85)
"""
현재 가격: 85
85 > 75 → 스택에서 (75, 4) 제거, 스팬 += 4
85 > 80 → 스택에서 (80, 1) 제거, 스팬 += 1
85 < 100 → 스택 유지
스택에 (85, 6) 추가
스팬 = 6
스택 상태: [(100, 1), (85, 6)]
"""
print(stockSpanner.next(85))  # 출력: 6

 

 

 

https://youtu.be/slYh0ZNEqSw?si=HZ33AtDoe__u0MjT

 

class StockSpanner:
    def __init__(self):
        # 스택 초기화: [가격, 스팬] 쌍을 저장
        self.stack = [] # pair: (price, span)

    def next(self, price: int) -> int:
        # 현재 날의 스팬은 최소 1 (오늘 포함)
        span = 1

        # 현재 가격이 스택의 맨 위 가격보다 크거나 같으면, 스택에서 꺼내며 스팬 누적
        while self.stack and self.stack[-1][0] <= price:
            # GPT 코드 (이게 좀더 명확한 것 같음)
            # _, prev_span = self.stack.pop()
            # span += prev_span  # 이전 날의 스팬을 더함
            span += self.stack[-1][1] # 이전 날의 스팬을 더함
            self.stack.pop() # 윗줄에서 span 에 추가한 것은 stack 에서 버림


        # 현재 가격과 계산된 스팬을 스택에 저장
        self.stack.append((price, span))

        # 현재 날의 스팬 반환
        return span
        


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)

 

 

두번째 시도 (2024.11.25, 월)

class StockSpanner:

    def __init__(self):
        self.daily_prices = []  # 가격을 저장하는 리스트
        self.daily_prices_len = 0  # 리스트 길이를 추적하는 변수

    def next(self, price: int) -> int:
        self.daily_prices.append(price)  # 새로운 가격 추가
        self.daily_prices_len += 1  # 리스트 길이 증가

        res = 0  # 현재 스팬 값을 저장하는 변수

        # 역순으로 리스트 탐색
        for i in range(self.daily_prices_len - 1, -1, -1):  
            if self.daily_prices[i] <= price:  # 현재 가격보다 작거나 같으면
                res += 1  # 스팬 값 증가
            else:
                break  # 조건을 만족하지 않으면 종료
                
        return res  # 최종 스팬 값 반환

 

Time Limit Exceeded

 

class StockSpanner:

    def __init__(self):
        # 스택을 초기화합니다. 스택에는 (주식 가격, 해당 가격에서의 스팬) 쌍을 저장합니다.
        self.stock = []  # a pair (price, days)

    def next(self, price: int) -> int:
        # 오늘 하루를 기본으로 스팬 값은 1로 설정
        day_count = 1  # today

        # 이전 주식 가격들과 비교하며 현재 가격보다 작거나 같은 가격을 제거
        # self.stock: 스택이 비어 있지 않고
        # self.stock[-1][0] <= price: 마지막 스택의 가격이 현재 가격보다 작거나 같으면
        while self.stock and self.stock[-1][0] <= price:
            # 마지막 스택을 꺼내서, 해당 가격의 스팬 값을 추가합니다.
            day_count += self.stock.pop()[1] 

        # 현재 주식 가격과 계산된 스팬을 스택에 추가
        self.stock.append((price, day_count))

        # 현재 주식 가격의 스팬 값을 반환
        return day_count

# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)

 

 

 

'LeetCode > LeetCode75' 카테고리의 다른 글

[LeetCode 75] Medium - 1071. Greatest Common Divisor of Strings ☆  (0) 2024.11.11
[LeetCode 75] Easy - 1768. Merge Strings Alternately  (0) 2024.11.11
[LeetCode 75] Medium - 739. Daily Temperatures  (0) 2024.11.10
[LeetCode 75] Medium - 435. Non-overlapping Intervals  (0) 2024.11.10
[LeetCode 75] Medium - 1268. Search Suggestions System  (0) 2024.11.09

'LeetCode/LeetCode75'의 다른글

  • 현재글[LeetCode 75] Medium - 901. Online Stock Span

관련글

티스토리툴바