프로그래머스 - 연속된 부분 수열의 합(Java)

투포인터 문제입니다.

 

투포인터란, 두 가지의 포인터를 사용해 배열에서 조건과 일치하는 연속된 부분을 찾을 수 있는 방법입니다.

조건에 맞춰 서로 다른 두 가지의 포인터를 움직여야 합니다.

 

입출력 예제 1번을 보도록 하겠습니다.

우선 left, right 라는 이름의 두 가지의 포인터를 배열 0번째 위치에 둡니다.

left와 right 사이가 부분 수열이 되는 것입니다.

현재 left와 right의 부분 수열의 합은 1입니다.

 

현재 부분 수열의 합이 k보다 작기 때문에 right를 움직입니다. (k = 7)

 

부분 수열이 [0, 1]가 되었습니다.

새로운 원소가 추가되었습니다.

기존의 부분 수열의 합에서 새로운 원소인 2를 더합니다.

그 합은 3입니다.

아직도 k보다 작기 때문에 right를 움직입니다.

 

부분 수열이 [0, 2]가 되었습니다.

새로운 원소가 추가되었습니다.

기존의 부분 수열의 합에서 새로운 원소인 3을 더합니다.

그 합은 6입니다.

아직도 k보다 작기 때문에 right를 움직입니다.

 

부분 수열이 [0, 3]가 되었습니다.

새로운 원소가 추가되었습니다.

기존의 부분 수열의 합에서 새로운 원소인 4를 더합니다.

그 합은 10입니다.

이번에는 부분 수열의 합이 k보다 크기 때문에 left를 움직입니다.

 

부분 수열이 [1, 3]가 되었습니다.

원소가 삭제되었습니다.

기존의 부분 수열의 합에서 1을 뺍니다.

그 합은 9입니다.

아직 부분 수열의 합이 k보다 크기 때문에 left를 움직입니다.

 

 

부분 수열이 [2, 3]가 되었습니다.

원소가 삭제되었습니다.

기존의 부분 수열의 합에서 2를 뺍니다.

그 합은 7입니다.

드디어 조건에 맞는 경우를 찾았습니다. 때문에, 정답 후보에 저장시켜둡니다.

 

아직 모든 조건을 탐색하지 못했습니다.

이 경우 right를 먼저 움직이되, right가 끝에 도달한 경우에는 left를 움직여야 합니다.

아직 right가 끝에 도달하지 못했으므로 right를 움직입니다.

 

부분 수열이 [2, 4]가 되었습니다.

새로운 원소가 추가되었습니다.

기존의 부분 수열의 합에서 새로운 원소인 5를 더합니다.

그 합은 12입니다.

right가 끝에 도달했고, 부분 수열의 합이 k보다 크기 때문에 left를 움직입니다.

 

부분 수열이 [3, 4]가 되었습니다.

원소가 삭제되었습니다.

기존의 부분 수열의 합에서 3을 뺍니다.

그 합은 9입니다.

이 역시 right가 끝에 도달했고, 부분 수열의 합이 k보다 크기 때문에 left를 움직입니다.

 

 

부분 수열이 [4, 4]가 되었습니다.

원소가 삭제되었습니다.

기존의 부분 수열의 합에서 4을 뺍니다.

그 합은 5입니다.

두 개의 포인터가 끝에 도달했습니다.

더이상 포인터를 움직일 수 없기 때문에 반복을 멈춥니다.

 

이처럼 서로 다른 두 개의 포인터를 사용하면 O(N)으로 문제를 해결할 수 있습니다.

 

[구현 코드]

import java.util.*;

class Solution {
    public int[] solution(int[] sequence, int k) {
        int left = 0;
        int right = 0;
        int partitionSum = sequence[0]; // 부분 수열의 합

        int n = sequence.length;

        List<SubSequence> subs = new ArrayList<>();
        while (true){
            // 현재 부분 수열의 합과 k가 일치하는 left와 right를 저장함
            if(partitionSum == k){
                subs.add(new SubSequence(left, right));
            }
            if(left == n && right == n) break;

            if(partitionSum <= k && right < n){
                right++;
                // 새로운 원소가 추가되었으므로, right에 위치하는 값을 부분 수열 합에 더함
                if(right < n) partitionSum += sequence[right];
            } else {
                // 기존의 left의 위치한 원소를 부분 수열의 합에서 제외
                if(left < n) partitionSum -= sequence[left];
                left++;
            }
        }

        // 조건에 가장 일치하는 부분 수열을 맨 앞으로 정렬
        subs.sort(SubSequence::compareTo);

        return new int[]{subs.get(0).left, subs.get(0).right};
    }
    
    private class SubSequence implements Comparable<SubSequence>{
        int left, right, size;

        public SubSequence(int left, int right) {
            this.left = left;
            this.right = right;
            this.size = right - left;
        }

        @Override
        public int compareTo(SubSequence o) {
            if(this.size == o.size){
                return this.left - o.left;
            }
            return this.size - o.size;
        }
    }
}