[프로그래머스] (Java) 연속된 부분 수열의 합 (투포인터, 슬라이딩 윈도우 알고리즘)

 

📑 1. 문제설명

---

💡 2. 접근방식

문제에서 주어진 매개변수

- 수열을 나타내는 정수 배열 `sequence`

- 부분 수열의 합을 나타내는 정수 `k`

 

조건을 만족하는 부분 수열의 시작 인덱스와 마지막 인덱스를 배열로 return하는 solution 함수를 작성하는 문제

---

 

투포인터, 슬라이딩 윈도우 알고리즘으로 푼다.

- start: 윈도우의 시작 인덱스
- end: 윈도우의 끝 인덱스 (or 다음 탐색할 위치)

 

`투포인터`

하나의 포인터는 배열의 시작을, 다른 하나는 배열의 끝을 가리키며 시작특정 조건을 만족하는 구간을 찾는것이다. 

 

`슬라이딩 윈도우 알고리즘`

부분 배열, 부분 문자열 문제에서 자주 사용되는 알고리즘으로 조건을 만족하는 구간을 찾거나, 고정된 크기 구간의 합계, 최대값, 최소값 등을 구할 때 유용하다. 고정크기와 가변크기의 구간 모두 탐색 가능한데 이 문제는 배열에서 합이 k인 가장 짧은 부분 배열을 구하는 가변 크기 탐색을 해야 한다.

---

⭐ 3. 정답코드

1. sum이 k보다 작은 동안 end값를 증가시키면서 더하기
2. sum이 k값과 같은 배열 구간중 len이 이전에 저장한 길이보다 짧다면 answer에 start와 end-1값을 저장하고, 새로운 길이(end-start)를 len에 저장
3. sum이 k이상이므로, sum에서 sequence[start]값을 빼준다.

class Solution {
    public int[] solution(int[] sequence, int k) {
        int[] answer = new int[2];
        int sum = 0;
        int start = 0;
        int end = 0;
        int len = -1;
        
        // start는 위에서 초기화 함
        // 누적합이 k보다 작은 구간 찾기
        for (; start < sequence.length; start++)  {
            while (end < sequence.length && sum < k) {
                sum += sequence[end++];
            }
            // 특정 조건을 만족하는 구간 (부분배열) 찾기 
            // 그중에서도 가장 짧은 길이를 가진 구간을 저장
            if (sum == k) {
                if(len == -1 || len > end - start) {
                    answer[0] = start;
                    answer[1] = end-1;
                    len = end - start;
                }
            }
            sum -= sequence[start];
        }
        return answer;
    }
}

 

✅  len== -1 하는 이유

if(len == -1 || len > end - start)

 

len은 현재까지 발견된 조건을 만족하는 부분 배열의 길이를 저장한다. 초기 상태에서는 길이를 비교할 기준이 없기 때문에 맨 위에서 len = -1로 초기화해서 "아직 어떠한 부분 배열도 선택되지 않았다"는 것을 선언을 해주었다. 조건을 만족하는 첫 번째 부분 배열이 발견되었을 때 이걸 반드시 채택하게 하는 구문이다. len == -1이 참이므로, 그 아래 answer에 start와end를 저장하는 코드가 실행된다.

 

✅ end-1인 이유

answer[1] = end-1;

 

위에서 sequence[end]의 값을 더한 후 end를 증가시키는 로직이 있기 때문에 루프가 종료될 때 end는 현재 부분 배열의 마지막 인덱스가 아니라 그 다음 인덱스를 가리키게 된다. 우리가 찾는 부분 배열의 실제 마지막 인덱스느느 `end - 1`이다.

while (end < sequence.length && sum < k) {
    sum += sequence[end++];
}

 

👏🏻 좋아요 가장 많이 받은 코드

원래 다른 코드가 좋아요 1위인데 오늘은 2위 코드가 더 간결하고 잘 쓴 거 같아서 가져옴

class Solution {
    public int[] solution(int[] sequence, int k) {
        int[] result = new int[2];
        int left = 0;
        int right = 0;
        int sum = 0;
        int minLength = Integer.MAX_VALUE;

        while (right < sequence.length) {
            sum += sequence[right];

            while (sum >= k) {
                if (sum == k && (right - left) < minLength) {
                    minLength = right - left;
                    result[0] = left;
                    result[1] = right;
                }
                sum -= sequence[left];
                left++;
            }
            right++;
        }

        return result;
    }
}

---

🐦 4. 같은 유형 문제