99클럽 코테 스터디 19일차 TIL Leetcode Count the Hidden Sequences

Leetcode Count the Hidden Sequences

이 문제는 differences라는 배열에 hidden 배열에 있는 알려지지 않은 연속된 숫자 2개의 차, 오른쪽 숫자에서 왼쪽 숫자를 뺀 값들이 저장되어있고, 그 hidden의 최소 최대 원소 값이 lower,upper형식으로 주어진다.

간단히 생각하면, 연속된 숫자의 차를 뺀 배열을 계속해서 더해가며, 0을 기준으로 시작했을때 얼마나 가장 커질수 있었는지, 작아질 수 있었는지를 기록하고, 그 폭의 길이가 lower과 upper 사이에 몇개 존재하는지 찾아내면 되는 문제이다.

이렇게 하면 O(N)의 시간 복잡도로 문제를 풀 수 있고, n의 범위가 1~10**5라서 널널하게 통과할 수 있다.

그렇게 간단히 구현한 나의 코드는 다음과 같다.

나의 코드

class Solution:
    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:
        diff_min=0
        diff_max=0
        acc=0
        for i in differences:
            acc+=i
            diff_min=min(diff_min,acc)
            diff_max=max(diff_max,acc)
        return max(0,(upper-lower)-(diff_max-diff_min)+1)