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

문제링크

문제접근

• 투 포인터로 이중반복문 돌지말자
• 비내림차순으로 정렬되어 있음
• 부분합 배열을 만들자
• left, right로 부분 수열 범위를 조절해가며 확인
• 합이 k가 되는 부분 수열 중 길이가 가장 짧은 놈이 답

코드

class Solution {
    public int[] solution(int[] sequence, int k) {
        int[] answer = new int[2];
        long[] sum = new long[sequence.length];
        sum[0] = sequence[0];
        if(sequence[0] == k){
            answer[0] = 0;
            answer[1] = 0;
            return answer;
        }
        for(int i=1;i<sequence.length;i++){
            sum[i] = sum[i-1] + sequence[i];
            if(sequence[i] == k){
                answer[0] = i;
                answer[1] = i;
                return answer;
            }
        }
        int left = 0;
        int right = 1;
        int answerLength = Integer.MAX_VALUE;
        while(left<sequence.length && right<sequence.length && left<right){
            long partSum;
            if(left == 0) partSum = sum[right];
            else partSum = sum[right] - sum[left-1];
            
            if(partSum == k){
                int nowLength = right - left + 1;
                if(nowLength < answerLength){
                    answer[0] = left;
                    answer[1] = right;
                    answerLength = nowLength;
                }
                left++;
            }
            else if(partSum > k){
                left++;
            }
            else if(partSum < k){
                right++;
            }
        }
        return answer;
    }
}

결과

정리

• 최근에 백준에서 투 포인터 문제 풀었던 접근법이 생각남