[PROGRAMMERS]연속된 부분 수열의 합

어떻게 풀지 감을 잡지 못하여 다른 분의 블로그를 참조하였다.

 

핵심은 투포인터 형식으로 풀어 나가는 것인데

 

left, right 처음에는 두 지점 모두 0번째 인덱스에서 시작하다가

 

처음으로 부분 수열의 합인 k 보다 커지게 되면 left를 상승시키고 기존에 넣었던 수를 빼낸다.

 

또는 처음으로 k와 같은 수를 만나게 되면 정답 후보에 넣는다.

 

또는 부분 수열의 합보다 값이면 right를 상승시키고 수를 하나 더 넣게 된다.

 

이를 반복하는데 right 및 left가 length를 벗어나게 되면 안되므로 해당 조건을 위한 if문을 적용하고 

 

right 상승시에도 right가 length 이상이면 배열 예외처리에 잡히므로 조건을 작성하였으며

 

left 상승시에도 마찬가지로 조건을 처리한다.

 

그리고, left와 right 상승 시점을 고려하여야 하는데 이는 left는 바뀐 위치의 것을 빼는 것이 아니므로 기존의 left 위치에서 빼기를 먼저 진행하고 right의 경우에는 위치를 업데이트 하고 값을 상승시켜야 적절한 처리가 되므로 위와 같은 처리를 두었다.

 

---

public class PRO_연속된_부분_수열의_합 {
    public static void main(String[] args) {
        int [] arr = solution(new int[]{1,1,1,2,3,4,5},5);

        for(int i = 0; i < arr.length; i++){
            System.out.println(arr[i] + " ");
        }
    }

    public static int[] solution(int[] sequence, int k) {
        int[] answer = new int[2];
        int left = 0;
        int right = 0;
        int ans = sequence[0];
        List<Sequence> list = new ArrayList<Sequence>();
        while(true){
            if (ans == k){
                list.add(new Sequence(left, right));
            }
            if(left == sequence.length && right == sequence.length){
                break;
            }
            
            if(ans <= k && right < sequence.length){
                right++;
                if(right < sequence.length){
                    ans += sequence[right];
                }
            }else{
                if(left < sequence.length)
                {
                    ans -= sequence[left];
                } 
                left++;
            }
        }
        Collections.sort(list);
        answer[0] = list.get(0).left;
        answer[1] = list.get(0).right;
        return answer;
    }
    public static class Sequence implements Comparable<Sequence>{
        int left;
        int right;
        int size;
        public Sequence(int left, int right) {
            this.left = left;
            this.right = right;
            this.size = right - left;
        }
        @Override
        public int compareTo(Sequence o) {
            if(this.size == o.size){
                return Integer.compare(this.left, o.left);
            }
            return this.size - o.size;
        }
        
    }
}