[프로그래머스] 연속된 부분 수열의 합

힌트

1. 목표 합을 찾기:
   • 주어진 배열에서 연속된 부분 배열의 합이 k가 되는 구간을 찾아야 합니다.
   • 시작점과 끝점 두 개의 포인터를 사용하여 배열을 탐색하며, 포인터 사이의 값들의 합이 k와 같은지 확인합니다.
2. 이동 방식:
   • 초기에는 배열의 시작에서 끝까지 포인터를 이동하면서 합계를 계산합니다.
   • 만약 현재 합이 k보다 크다면 시작 포인터를 앞으로 이동시켜 구간을 줄입니다.
   • 합이 정확히 k가 되면 해당 구간을 기록하고, 더 짧은 구간이 있을 경우 그것으로 업데이트합니다.
3. 최적화 방법:
   • 각 구간에서의 합을 실시간으로 유지하며, 불필요한 연산을 줄이기 위해 더 짧은 구간이 발견될 때만 결과를 업데이트합니다.
   • 탐색이 끝날 때까지 가장 짧은 구간을 찾아냅니다.

 

---

정답은 더보기 클릭

class Solution {
    public int[] solution(int[] sequence, int k) {
        int[] result = new int[2];  // 결과를 담을 배열 (시작, 끝 인덱스)
        
        int s = 0;  // 시작 포인터
        int e = 0;  // 끝 포인터
        
        int sum = 0;  // 현재 구간의 합을 저장
        int min = Integer.MAX_VALUE;  // 최소 구간 길이를 저장하기 위한 변수
        while (e < sequence.length) {  // 끝 포인터가 배열 끝에 도달할 때까지 반복
            sum += sequence[e++];  // 끝 포인터를 이동하며 현재 구간의 합을 더함
            
            // 구간의 합이 k보다 크다면, 시작 포인터를 이동하여 합을 줄임
            while (sum > k) {
                sum -= sequence[s++];
            }
            
            // 구간의 합이 정확히 k이고, 더 짧은 구간이라면 결과를 업데이트
            if (sum == k && min > e - s - 1 ) {
                result[0] = s;  // 시작 인덱스 저장
                result[1] = e-1;  // 끝 인덱스 저장
                min = e - s - 1;  // 최소 구간 길이 갱신
            }
        }
        
        return result;  // 최종 구간 반환
    }
}