99클럽 코테 스터디 28일차 TIL - 배열 (LeetCode 2145번)

항해99 코테 스터디 28일차 문제인 리트코드의 2145번은 어떤 배열의 연속된 요소의 차이를 담은 배열을 통해 구할 수 있는 원본 배열의 개수를 구하는 문제다. 난이도는 Medium이다.

 

오늘의 문제 - 2145. Count the Hidden Sequences 문제 정보

문제 키워드

- 배열

난이도

- Medium

 

문제 요약

• differences[i] = hidden[i+1] - hidden[i]
  • hidden.length = n+1, differences.length = n
• hidden의 값의 범위 [lower, upper]가 주어질 때, 가능한 hidden의 개수를 구하여라.

 

문제 풀이 과정  

•  

• 연속된 값의 차이가 모두 주어지기 때문에 값이 하나면 정해지면 나머지 요소들이 전부 정해진다. 따라서 모든 요소를 하나의 미지수를 이용해 나타낼 수 있고, 최댓값과 최솟값도 정해진다.
  • differences = [3,-4,5,1,-2], lower=-4, upper=5
    • hidden = [x,x+3,x-1,x+4,x+5,x+3], max=x+5, min=x-1
    • x+5≤5, x-1≥-4 → -3 ≤ x ≤ 0 → x=-3,-2,-1,0 → 답: 4
  • 그리고 이를 구하는 과정은 O(n)이다.

 

코드

class Solution {
    public int numberOfArrays(int[] differences, int lower, int upper) {
        int preVal = 0;
        int maxVal = 0, minVal = 0;
        int maxDiff = upper - lower;

        // diff를 하나씩 살펴보며, hidden의 최댓값과 최솟값을 구함
        for(int i=0; i<differences.length; i++) {
            int nowVal = preVal + differences[i];
            maxVal = Integer.max(maxVal, nowVal);
            minVal = Integer.min(minVal, nowVal);

            // 만약 현재의 최댓값과 최솟값의 차이가
            // 차이값의 최대를 벗어났다면 바로 0 반환하고 종료
            if (maxVal - minVal > maxDiff) {
                return 0;
            }

            preVal = nowVal;
        }

        // 기준값(hidden[0])의 최댓값과 최솟값을 구함
        int max = upper - maxVal;
        int min = lower - minVal;

        // 최솟값에서 최댓값까지의 개수를 정답으로 반환
        return max >= min ? max - min + 1 : 0;
    }
}

• 시간복잡도: O(n)
• 공간복잡도: O(1)

 

오늘의 학습 회고

• 드디어 목표 일자인 28일 채웠다! 문제를 매일 풀고 TIL을 꾸준히 쓰니까 점점 문제에 대한 파악 속도도 빨라지고 방향성도 빨리 잡게되는 것 같아서 좋다.