1. 문제 소개

2110. Number of Smooth Descent Periods of a Stock

2. 나의 풀이

배열을 순회하며 문제의 조건에 맞는 부분을 찾고, 부분배열의 숫자의 팩토리얼만큼 늘어난다는 사실을 발견했다.
풀이의 시간복잡도는 $O(n)$이다.

class Solution:
    def getDescentPeriods(self, prices: List[int]) -> int:
        n = len(prices)        # 가격 배열의 길이
        ans, prev = 1, 1       # ans: 전체 descent period 수
                               # prev: 현재 인덱스에서 끝나는 descent period의 길이
        
        # 두 번째 원소부터 순회하며 이전 가격과의 차이를 확인
        for i in range(1, n):
            # 바로 전날 가격이 오늘 가격보다 정확히 1 큰 경우
            if prices[i-1] - prices[i] == 1:
                prev += 1      # 이전 descent 구간에 이어서 길이 증가
            else:
                prev = 1       # 조건이 깨지면 새 구간 시작 (길이 1)
            ans += prev        # 현재 위치에서 끝나는 모든 descent 구간을 누적
        
        return ans             # 전체 smooth descent period 개수 반환

3. 다른 풀이

다른 풀이의 경우에도 배열을 순회하는 것은 똑같지만 부분합을 따로 계산하는 방식을 사용했다.
똑같은 시간복잡도를 갖는다.

class Solution:
    def getDescentPeriods(self, prices: List[int]) -> int:

        tally, ans = 1, 0
        # tally: 현재 연속된 smooth descent 구간의 길이
        # ans: 전체 smooth descent period의 누적 개수

        triangle = lambda x: x * (x + 1) // 2
        # 길이가 x인 연속 구간에서 만들 수 있는 부분 구간 개수
        # = 1 + 2 + ... + x = x(x+1)/2

        # 인접한 두 가격 (p1, p2)를 순회
        for p1, p2 in pairwise(prices):
            # 바로 전날 대비 정확히 1 감소한 경우
            if p2 == p1 - 1:
                tally += 1          # 현재 descent 구간 길이 증가
            else:
                # descent 조건이 끊기면,
                # 지금까지 누적된 구간 길이로 만들 수 있는 모든 부분 구간을 더함
                ans += triangle(tally)
                tally = 1           # 새로운 구간 시작 (자기 자신만 포함)

        # 마지막 descent 구간에 대해서도 동일하게 처리
        ans += triangle(tally)

        return ans

4. 마무리

어렵지 않은 문제였다.