[Programmers] 연속된 부분 수열의 합

https://school.programmers.co.kr/learn/courses/30/lessons/178870

프로그래머스

문제 설명

기본적인 투 포인터 문제이다. 먼저 완전 탐색으로 해결하니 많은 테스트 케이스에서 시간 초과가 발생했고 투 포인터로 해결하였다.

원리는 간단하다. 왼쪽과 오른쪽 포인터 변수를 하나씩 둔다. sum에 누적합 결과를 저장한다. 만약 sum이 k보다 작으면 오른쪽 포인터를 오른쪽으로 이동시키면서 누적합 계산을 한다. 그러다 k와 같아지면 범위 비교를 한다. 그렇게 해서 더 간격이 좁은 구간의 포인터 값을 저장한다. 만약 sum이 k보다 커지면 왼쪽 포인터 변수를 오른쪽으로 이동시키면서 그 값을 빼준다. R < len 조건을 추가한 이유는 R이 배열 범위를 넘어갔을 경우를 처리하기 위해서다. 두 번째 테스크 케이스인 [1, 1, 1, 1, 2, 3, 4, 5] 와 같은 경우이다. R은 이미 끝까지 가서 더 갈 곳이 없지만 L을 계속 빼가면서 범위 계산을 해야 하기 때문이다.

투 포인터 코드

class Solution {
    public int[] solution(int[] sequence, int k) {
        int len = sequence.length;
        int left = 0, right = len; // 정답을 담는 변수
        int L = 0, R = 0;          // 포인터 변수
        int sum = 0;
        
        while (L < len) {
            while (R < len && sum < k) {
                sum += sequence[R++];
            }
            
            if (sum == k) {
                int range = (R - 1) - L;
                if ((right - left) > range) {
                    left = L;
                    right = R - 1;
                }
            }
            
            sum -= sequence[L++];
        }
        
        return new int[] {left, right};
    }
}

완전 탐색 코드

class Solution {
    public int[] solution(int[] sequence, int k) {
        int len = sequence.length;
        int left = 0, right = len;
        
        for (int L = 0; L < len; L++) {
            int sum = 0;
            for (int R = L; R < len; R++) {
                sum += sequence[R];
                if (sum == k) {
                    int range = R - L;
                    if ((right - left) > range) {
                        left = L;
                        right = R;
                    }
                } else if (sum > k) {
                    break;
                }
            }
        }
        
        return new int[] {left, right};
    }
}