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

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

프로그래머스

코딩테스트 연습 > 연습문제 > 연속된 부분 수열의 합

 

문제 접근

투포인터 문제!!

 

시작 min = Integer.MAX_VALUE(약 21억) 

 

누적값이 k랑 같고 연속된 부분 수열의 길이가 min 보다 작으면 갱신한다. 

길이 갱신: min = end - start + 1;

index 갱신:  answer_st = start; , answer_en = end - 1;

 

같으면 무시한다. 

길이가 짧은 수열이 여러 개인 경우 가장 앞쪽(시작 인덱스가 작은)에 나오는 수열이 정답 

나는 수열의 합을 맨 앞 index 즉 0부터 찾을 거니 같으면 무시하면 된다.

 

문제에서 수열의 합이 k가 아닌 경우가 있다는 설명은 없다 

그럼 딱히 예외 처리를 할 부분은 없다.  

 

주의!

k는 최대가 10억이다. 

즉 수열의 합 기록도 long으로 해야 한다. 

 

핵심 로직

end index를 증가한다. 

end index에 해당하는 값을 cur에 추가한다. 

 

3가지 case 

 

k보다 cur이 작으면 더 이상 해줄 게 없다. continue 

 

만약 cur == k && min 보다 현재 수열의 길이가 작다면 갱신!

 

cur이 k 보다 더 크다면 작거나 같아질 때까지 start 인덱스에 해당하는 값을 빼주고 start 인덱스를 증가한다. 

중요! 이 순간에 cur == k 인 case가 있다. 만약 수열의 길이가 작다면 갱신해 준다.

for(int i = 0; i < sequence.length; i++){
    end++;
    cur += sequence[i];
    if(cur < k) continue;

    if(cur == k){
        if(min > end - start + 1){
            min = end - start + 1;
            answer_st = start;
            answer_en = end - 1;
        }
    }
    else{
        while(cur > k){
            cur -= sequence[start++];
        }
        if(cur == k){
            if(min > end - start + 1){
                min = end - start + 1;
                answer_st = start;
                answer_en = end - 1;
            }
        } 
    }
}

 

전체 코드

import java.util.*;
class Solution {
    public int[] solution(int[] sequence, long k) {
        int min = Integer.MAX_VALUE;
        int start = 0;
        int end   = 0;
        long cur  = 0;
        int answer_st = -1;
        int answer_en = -1; 
        for(int i = 0; i < sequence.length; i++){
            end++;
            cur += sequence[i];
            if(cur < k) continue;
            if(cur == k){
                if(min > end - start + 1){
                    min = end - start + 1;
                    answer_st = start;
                    answer_en = end - 1;
                }
            }
            else{
                while(cur > k){
                    cur -= sequence[start++];
                }
                if(cur == k){
                    if(min > end - start + 1){
                        min = end - start + 1;
                        answer_st = start;
                        answer_en = end - 1;
                    }
                } 
            }
        }
        return new int []{answer_st, answer_en};
    }   
}