[Python] 2145. Count the Hidden Sequences

 

https://leetcode.com/problems/count-the-hidden-sequences/description/

 

문제설명

• n개의 숫자로  구성된 differences라는 1차원 배열이 주어진다. 
• 이 differences 배열은 값들의 차이를 의미하는 것으로 정답이 될 수 있는 리스트를 Temp 라고 할때 differences[i] = Temp[i+1] - Temp[i]이다.
• 정답이 될 수 있는 리스트 Temp의 모든 숫자는 lower와 upper 사이에 있어야 합니다.
• differences와 lower,upper가 주어졌을 때 해당 조건을 만족할 수 있는 리스트의 개수를 반환하는 문제이다.

 

접근법

• 0에서부터 differences값을 하나씩 더해서 누적합을 구한다. 이 과정에서 min값과 max 값을 구해서 0을 기준으로 +- 몇이 차이가 나는지 구한다. (값이 변하는 범위를 구한다.)
• 0을 기준으로 구했던 min, max를 lower와 upper 기준으로 업데이트 한다.
  이 때 lower값과 min값이 각각 음수인지, 양수인지에 따라 각기 다른 기준으로 업데이트 한다. 
• min과 max를 이용하여 조건을 만족할 수 있는 리스트의 첫번째 값의 개수를 구한다.
  이 과정에서 min > max면 문제 조건대로 0을 리턴한다.
• (지금와서 생각해보면 max값이 음수인 것은 고려가 안된 것 같기도...)

1번 예제에 대해서 설명해보겠다.
Input: differences = [1,-3,4], lower = 1, upper = 6 

differences의 누적합을 구하면 [0, 1, -2, 2]가 될 것이다. 
누적합 중 min은 -2, max는 2가 될 것이다.

max = upper - max로  4가 된다. 
min = lower + -(min) 로 3이 된다.

위 조건으로 만들 수 있는 리스트의 첫번째 값이 될 수 있는 범위는 3~4가 되므로 2가 리턴된다.

class Solution:
    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:
        min = 0
        max = 0

        # 누적합 중 최소와 최댓값을 찾음
        cur_num = 0
        for diff in differences:
            cur_num += diff
            if cur_num < min:
                min = cur_num
            elif cur_num > max:
                max = cur_num

        # lower와 upper 기준으로 min, max값 업데이트
        max = upper - max
        if (lower > 0 and min < 0) or (lower < 0 and min < 0):
            min = lower + -(min)
        else:
            min = lower + min

        if min > max:
            return 0
        else:
            return max - min + 1