⭐연속된 부분 수열의 합

프로그래머스 문제 링크

풀이

사용언어 : JAVA

풀이 1 : 시간 초과

1. 누적합을 이용해 부분 수열의 합이 k를 만족하는 배열의 시작과 끝 idx를 answerStart와 answerEnd저장한다.
2. maxSize에 부분 수열의 길이를 저장하고, 부분 수열의 합이 k를 만족하는 배열의 길이를 비교해 작을 경우 answerStart와 answerEnd를 바꾸어주기.

class Solution {
    public int[] solution(int[] sequence, int k) {
        int[] cal = new int[sequence.length];
        cal[0] = sequence[0];
        // 누적합을 저장
        for(int i = 1; i < sequence.length; i++) {
            cal[i] = cal[i-1] + sequence[i];
        }
        int answerEnd = 0;
        int answerStart = 0;
        int maxSize = sequence.length;
        
        for(int i = 0; i < sequence.length; i++) {
            if (maxSize == 1) {
                break;
            }
            if(cal[i] < k) continue;
            if(cal[i] == k){
                if(maxSize > i){
                    answerEnd = i;
                    answerStart = -1;
                    maxSize = i+1;
                }
                continue;
            }
            
            for(int j = i-1; j >= answerStart; j--){
                if(cal[i] - cal[j] > k || i-j >= maxSize ){
                    break;
                }
                
                if(cal[i] - cal[j] == k && i-j < maxSize) {
                    answerEnd = i;
                    answerStart = j;
                    maxSize = i-j;
                    break;
                }
                
            }
           
        }
        
        int[] answer = {answerStart+1, answerEnd};
        return answer;
    }
}

풀이 2 : ⭐통과⭐

투포인터 알고리즘을 활용

투포인터 알고리즘이란?
리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘

while문을 사용해 sum(부분 수열의 합)을 구합니다.
만약 sum이 k일 경우 배열의 길이을 구하고 left, right와 비교해 arraySize가 작을경우 left와 right를 갱신 시켜줍니다.

마지막으로 l을 옮기면서 sum에서 sequence[l]을 빼줍니다.

class Solution {
    public int[] solution(int[] sequence, int k) {
        
        int n = sequence.length;
        int left = 0;
        int right = n;
        int sum = 0;
        for(int l = 0, r = 0; l < n; l++){
            while(r < n && sum < k) {
                sum+= sequence[r++];
            }
            
            if(sum == k) {
                int arraySize = r - l -1;
                if((right-left) > arraySize ) {
                    left = l;
                    right = r - 1;
                }
            }
            
            sum -= sequence[l];
            
        }
        int[] answer = {left, right};
        return answer;
    }
}