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

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/178870

이 문제는 투 포인터 알고리즘을 이용하여 풀 수 있습니다. 투 포인터 알고리즘이란 배열이나 리스트와 같은 선형 자료 구조에서 두 개의 포인터를 사용하여 특정 조건을 만족하는 원소를 찾거나 "부분 배열, 부분 리스트"를 처리하는데 사용되는 알고리즘입니다. 투 포인터 알고리즘은 다음의 방식으로 동작합니다.

1. 배열이나 리스트의 시작 지점에서 첫 번째 원소를 가리키는 포인터와 마지막 원소를 가리키는 포인터를 초기화
2. 두 포인터 사이의 원소나 부분 배열을 조사하고 조건을 만족하는지 확인
   2-1. 조건을 만족하지 않으면 한 포인터를 이용
3. 조건을 만족하는 원소나 부분 배열을 찾고나 끝까지 탐색할때까지 반복

이번 문제는 왼쪽 및 오른쪽 포인터를 0으로 초기화한 후 합이 k와 같을 때까지(조건) 오른쪽 포인터를 증가시키면서 합이 같을 경우 기존 포인터와의 길이를 구해 길이가 더 짧을 경우 해당 값으로 치환하고 왼쪽 포인터를 증가시키는 방식으로 풀 수 있습니다.

여기서 주의할 점은 아래 코드의 경우 오른쪽 포인터를 ++을 이용해서 증가시켰는데 합이 만족된 경우에도 포인터가 이동하여 오른쪽 포인터를 -1하지 않으면 다음 포인터를 참조하여 잘못된 결과가 발생합니다. 따라서 이 부분을 주의해서 처리해주면 됩니다.

다음은 코드입니다.

import java.util.*;

class Solution {
    public int[] solution(int[] sequence, int k) {
        int N = sequence.length;
        
        int left = 0; int right = N-1;
        int sum = 0;
        
        int L = 0; int R = 0;
        for(int i=0;i<sequence.length;i++){
            while(R < N && sum < k){
                sum += sequence[R++];
            }
            
            if(sum == k){
                int range = R-1 -L;
                if(range < right - left){
                    left = L;
                    right = R-1;
                }
            }
            
            sum -= sequence[L++];
        }
        
        int[] answer = {left,right};
        return answer;
    }
}