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

https://school.programmers.co.kr/learn/courses/30/lessons/178870?language=java 

프로그래머스

 

문제

비내림차순으로 정렬된 수열이 주어졌을 때 수열의 구간 합이 K 값이 되는 구간 인덱스를 구하는 문제

 

비내림차순이면 오름차순인거지 왜 비내림차순 이렇게 적은지는 모르겠다 

 

수열은 오름차순으로 되어있고 어느 구간을 뽑든 수열을 만족한다. 

K 값이 되는 구간이 여러 개일 경우, 구간이 가장 적으며 가장 앞에있는 수열을 출력하면 된다. 

 

---

풀이

구간을 정해야하기 때문에

 

왼쪽 인덱스 , 오른쪽 인덱스 로 구분해서 풀었다. 

 

left ~ right 사이의 값이 K 보다 크면 left 를 +1 하고

작거나 같으면 right를 +1로 갱신한다. 

 

인덱스를 갱신한 만큼 구간 합에 더하거나 빼주면 된다. 

---

class Solution {
    public int[] solution(int[] sequence, int k) {
        int[] answer = {};
        
        int min_left = 0;
        int min_right = sequence.length;
        
        int left = 0;
        int right = 0;
        int sum = sequence[0];
        
        while(left < sequence.length && right < sequence.length) {
            if (sequence[left] > k) {
                break;
            }
            
            if (sum == k) {
                if (min_right - min_left > right-left) {
                    min_left = left;
                    min_right = right;
                } else if (min_right - min_left == right - left) {
                    if (min_left > left) {
                        min_left = left;
                        min_right = right;
                    }
                }

            }
            
            if (sum <= k) {
                right++;
                if (right < sequence.length) {
                    sum += sequence[right];
                }
            } else {
                sum -= sequence[left];
                left++;
            }
        }
        
        answer = new int[]{min_left, min_right};
        return answer;
    }
}