[리트코드][JAVA] 2145. count-the-hidden-sequences(숨겨진 시퀀스 계산)

💡 문제
count-the-hidden-sequences (https://leetcode.com/problems/count-the-hidden-sequences/description/)
자세한 문제 설명과 입출력 예는 링크를 참고해주세요.

 

📝 선행 개념

1. 배열과 인덱스 관계 이해

주어진 문제에서는 배열 differences가 주어지고, 이 배열은 숨겨진 수열의 연속된 요소들 사이의 차이를 나타냅니다. 예를 들어, differences[i] = hidden[i + 1] - hidden[i]와 같이 정의됩니다. 따라서 숨겨진 수열의 각 요소는 이 차이들을 이용해 추정할 수 있습니다.

2. 숨겨진 수열의 범위 제한

문제는 숨겨진 수열이 특정한 범위 [lower, upper]에 속하는 값들만 포함해야 한다는 것입니다. 이는 가능한 숨겨진 수열을 결정하는 중요한 제한 조건입니다.

3. 가능한 숨겨진 수열의 조건

• 숨겨진 수열의 길이는 n + 1이어야 합니다 (n은 differences 배열의 길이).
• 각 숨겨진 수열의 요소는 주어진 differences 배열을 이용해 추론할 수 있어야 합니다.
• 숨겨진 수열의 각 요소는 [lower, upper] 범위 내에 있어야 합니다.

4. 가능한 숨겨진 수열의 개수 구하기

주어진 differences 배열과 [lower, upper] 범위 내에서 가능한 모든 숨겨진 수열을 찾고, 그 개수를 반환해야 합니다. 이는 유효한 숨겨진 수열을 모두 생성하고 조건을 만족하는 것을 세는 작업입니다.

---

🤓 문제 풀이

🔨 문제 설명

제목:2145. 숨겨진 시퀀스 계산

설명:

길이가 숨겨진 시퀀스 의 각 연속 정수 쌍 간의 차이를 설명하는 0부터 인덱스가 지정된n 정수 배열이 제공됩니다 . 더 공식적으로는 숨겨진 시퀀스를 호출하면 가 됩니다 .differences(n + 1)hiddendifferences[i] = hidden[i + 1] - hidden[i]

또한 숨겨진 시퀀스에 포함될 수 있는 값의 포괄적인 범위를 설명하는 lower두 개의 정수가 제공됩니다 .upper[lower, upper]

• 예를 들어, , , 가 주어 differences = [1, -3, 4]lower = 1upper = 6416은닉 시퀀스는 요소가 과 ( 포함 ) 사이에 있는
  • [3, 4, 1, 5][4, 5, 2, 6]
  • 가능한 숨겨진 시퀀스입니다 .
  • [5, 6, 3, 7]6
  • 보다 큰 요소가 포함되어 있으므로 불가능합니다
  • [1, 2, 3, 4]
  • 차이가 정확하지 않기 때문에 불가능합니다.
• 길이의 시퀀스입니다 .
• 지면

가능한 숨겨진 시퀀스 의 수를 반환합니다 . 가능한 시퀀스가 없으면 를 반환합니다

 

이 문제는 differences 배열을 기반으로 주어진 구간 [lower, upper] 내에서 가능한 숨겨진 수열의 개수를 찾는 것입니다. 주어진 differences 배열은 연속된 두 수의 차이를 나타냅니다. 따라서 숨겨진 수열의 첫 번째 요소를 기준으로 나머지 요소들을 유도할 수 있습니다.

---

🔨 접근 방법

• Difference 배열의 활용:
  • 문제에서 주어지는 differences 배열은 인접한 두 숫자 간의 차이를 나타냅니다. 이를 통해 숨겨진 수열의 첫 번째 숫자부터 나머지 숫자들을 계산할 수 있습니다.
  • 예를 들어, differences = [1, -3, 4]라면 숨겨진 수열의 첫 번째 숫자를 start로 두고, 순서대로 start + differences[0], (start + differences[0]) + differences[1], ..., 을 계산하여 숨겨진 수열을 재구성할 수 있습니다.
• 수열의 범위 확인:
  • 문제에서는 숨겨진 수열의 값들이 [lower, upper] 범위 내에 있어야 한다고 명시했습니다. 따라서 우리는 각 숨겨진 수열의 값이 이 범위에 속하는지를 확인해야 합니다.
  • 이를 위해 min_val과 max_val을 사용하여 숨겨진 수열의 최소값과 최대값을 추적합니다. 여기서 min_val은 숨겨진 수열의 최소값이 되도록 계산하고, max_val은 숨겨진 수열의 최대값이 되도록 계산합니다.
• 시작점의 계산:
  • 가능한 숨겨진 수열의 첫 번째 숫자 start는 differences 배열을 기반으로 한정된 범위 내에서 결정됩니다.
  • start가 결정되면, 이를 기준으로 hidden 배열의 나머지 요소들을 계산하고, 모든 요소가 [lower, upper] 범위에 속하는지를 확인합니다.
• 위의 접근 방법을 바탕으로 코드를 구현할 때는 min_val, max_val을 초기화하고, start의 가능한 범위를 계산하여 가능한 모든 start에 대해 숨겨진 수열의 요소들이 주어진 범위 내에 속하는지를 검사합니다. 이후 가능한 start의 개수를 세어 반환합니다.

---

🔨 문제 풀이 과정

• 숨겨진 수열의 유도:
  • hidden 배열의 첫 번째 요소를 start라고 가정합니다.
  • differences 배열을 사용하여 나머지 요소들을 유도할 수 있습니다. hidden[i + 1] = hidden[i] + differences[i] 식을 사용하여 계산합니다.
  • 즉, hidden[1] = start + differences[0], hidden[2] = hidden[1] + differences[1], ... 이런 식으로 계속 진행됩니다.
• 범위 확인:
  • 유도된 hidden 배열의 모든 요소가 [lower, upper] 구간 내에 있어야 합니다.
  • 이를 위해 각 요소의 최솟값(min_val)과 최댓값(max_val)을 추적합니다. 초기값은 start로 설정합니다.
  • start를 기준으로 각 differences 값을 더하거나 빼면서 min_val과 max_val을 갱신합니다.
• 가능한 시작점 계산:
  • 모든 유도된 hidden 배열의 요소가 [lower, upper] 내에 있어야 하므로, min_val과 max_val을 기준으로 가능한 시작점(start)의 범위를 계산합니다.
  • 가능한 시작점의 범위는 lower - min_val부터 upper - max_val 사이에 있습니다.
  • 이 범위 내에 있는 정수 개수를 세면 됩니다.

---

🔨 Greedy Algorithm (탐욕)

이 문제는 특정한 알고리즘 개념을 사용하는 것보다는 문제를 푸는 전략과 접근 방식이 중요합니다. 여기서 사용된 것은 **Greedy Algorithm (탐욕 알고리즘)**의 개념을 활용한 방법입니다. Greedy Algorithm은 각 단계에서 가장 좋은 선택을 하는 방식으로 문제를 해결하는 알고리즘입니다.

1. 숨겨진 수열 유도:
   • differences 배열을 사용하여 숨겨진 수열의 첫 번째 숫자 start를 가정하고, 이를 기반으로 숨겨진 수열의 나머지 요소들을 차례로 계산했습니다. 각 요소는 이전 요소와 differences 배열의 값을 더함으로써 유도되었습니다.
2. 범위 검사:
   • 숨겨진 수열의 각 요소가 [lower, upper] 범위 내에 있는지 확인하기 위해, 각 요소의 최소값(min_val)과 최대값(max_val)을 추적했습니다. 이 값을 계속 갱신하며 숨겨진 수열의 모든 요소가 주어진 범위 내에 있는지를 검사했습니다.
3. 가능한 시작점 계산:
   • 가능한 숨겨진 수열의 첫 번째 숫자 start의 범위를 계산하여, 이 범위 내에서 가능한 모든 start를 고려했습니다. 이를 통해 가능한 모든 숨겨진 수열의 경우를 탐색하고 검증할 수 있었습니다.

따라서 이 문제는 Greedy Algorithm의 아이디어를 사용하여 문제를 해결하는 것이라고 할 수 있습니다. Greedy Algorithm은 매 단계에서 현재 상황에서 가장 최적의 선택을 하는 방식으로, 문제를 효율적으로 해결할 수 있는 경우가 많습니다.

---

🔨 구현코드

class Solution {
    public int numberOfArrays(int[] differences, int lower, int upper) {
        // 숨겨진 수열의 가능한 최소값과 최대값 초기화
        long min_val = 0;
        long max_val = 0;
        long current = 0;

        // differences 배열을 사용하여 hidden 배열의 값 갱신 (differences 배열을 순회하며 최소값과 최대값 계산)
        for (int diff : differences) {
            current += diff;
            min_val = Math.min(min_val, current);
            max_val = Math.max(max_val, current);
        }

        // 가능한 시작점(start)의 범위 계산
        long min_start = lower - min_val;
        long max_start = upper - max_val;

        // 가능한 숨겨진 수열의 개수 계산
        long result = Math.max(0, max_start - min_start + 1);

        return (int) result;
    }
}

---

📚 풀이 보완

코드 설명

1. 변수 초기화:
   • min_val, max_val은 start를 기준으로 hidden 배열의 최소값과 최대값을 추적합니다.
   • current는 start로부터 differences 값을 차례로 더해가면서 현재 값을 추적합니다.
2. differences 배열 처리:
   • 각 differences 값을 current에 더합니다.
   • 이 때마다 min_val과 max_val을 갱신합니다.
3. 가능한 시작점 계산:
   • min_start는 lower - min_val로, max_start는 upper - max_val로 계산합니다.
   • 가능한 시작점의 개수는 max_start - min_start + 1 입니다. 이 값이 음수일 경우 가능한 시작점이 없다는 의미이므로 0으로 설정합니다.

---

📍 Plus+

공간 복잡도

• 변수 사용: min_val, max_val, current, min_start, max_start 등 여러 변수를 사용합니다. 각 변수는 long 타입이므로 상수 크기의 메모리를 사용합니다.
• 추가 공간: 추가적으로 n개의 differences 배열이 입력으로 주어지지만, 이는 입력의 일부로 간주되므로 공간 복잡도에 추가적인 영향을 주지 않습니다.
• 공간 복잡도: 사용된 변수들이 모두 상수 크기의 메모리를 사용하므로, 공간 복잡도는 O(1)입니다.

시간복잡도

• 루프:
  • for (int diff : differences) 루프를 통해 differences 배열의 모든 요소를 한 번씩 순회합니다. 이 과정은 O(n) 시간이 소요됩니다 (n은 differences 배열의 길이).
• 연산: 각 루프에서는 current 값을 업데이트하고, min_val과 max_val을 업데이트하는 연산이 수행됩니다. 이는 각각 상수 시간 복잡도인 O(1)입니다.
• 최종 계산 및 반환: max_start - min_start + 1을 계산하고 이 값을 Math.max(0, ...)을 통해 음수인 경우 0으로 처리한 후, int로 캐스팅하여 반환합니다. 이 연산 또한 상수 시간이 소요됩니다.

따라서 전체 시간 복잡도는 O(n)입니다. 입력 배열 differences의 길이에 선형으로 비례하여 수행 시간이 증가합니다. 공간 복잡도는 추가적인 배열이나 자료 구조를 사용하지 않고 상수 크기의 메모리를 사용하므로 O(1)입니다.

요약

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

---

다른방법의 풀이

 

동적 계획법 (Dynamic Programming)을 이용한 방법