[Programmers/JAVA] 04. 연속된 부분 수열의 합

※  연속된 부분 수열의 합

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

 

 

문제 분석

오름차순으로 정렬된 수열 sequence 와 부분 수열의 합을 나타내는 정수 k 가 매개변수로 주어진다.

원소의 합이 k 인 부분 수열을 찾을 때, 부분 수열의 시작 인덱스와 마지막 인덱스를 구하는 문제이다.

단, 합이 k 인 수열이 여러 개인 경우 길이가 짧은 수열을 찾고, 길이가 같은 경우 시작 인덱스가 작은 수열을 찾는다.

 

접근 방법

 슬라이딩 윈도우  방식을 사용하여 합이 k 인 수열 중 조건에 맞는 수열을 찾을 것이다.

윈도우의 시작과 마지막 인덱스를 모두 0에서 시작한다.

시작 인덱스부터 마지막 인덱스 사이의 합이 k 보다 작으면 마지막 인덱스를 오른쪽으로 한 칸 이동시킨다.

시작 인덱스부터 마지막 인덱스 사이의 합이 k 보다 크다면 시작 인덱스를 오른쪽으로 한 칸 이동시킨다.

시작 인덱스부터 마지막 인덱스 사이의 합이 k 와 같다면 이전에 설정된 값과 우선 순위를 비교하여 교체한다.

마지막 인덱스에서 시작 인덱스를 뺀 값이 작을 수록 우선 순위가 높다.

 

시작 인덱스와 마지막 인덱스가 $0$부터 $N$까지 이동하므로 시간 복잡도는 $O(2N) == O(N)$이다.

 

 

※  투 포인터 vs 슬라이딩 윈도우

투 포인터 방식과 슬라이딩 윈도우 방식 모두 두 개의 포인터를 사용하는 기법이지만 방식에 차이가 있다.

투 포인터 방식에서는 두 포인터가 서로 다른 방향으로 이동한다.
주로 정렬된 배열에서 두 수의 합이 특정 값이 되는 경우나 두 배열의 공통 원소를 찾는 문제에서 사용된다.
즉, 두 요소 간의 관계를 바탕으로 하는 문제에서 주로 사용된다.

슬라이딩 윈도우 방식에서는 두 포인터가 같은 방향으로 이동한다.
주로 최대 길이의 부분 문자열 찾는 문제나 부분 배열의 합이 특정 값을 넘지 않도록 하는 문제에서 사용된다.
즉, 특정 구간을 정의하고 그 구간에서 최적의 결과를 찾는 문제에서 주로 사용된다.

 

코드 설계

 

# 시작과 마지막 인덱스를 저장한 배열 result 를 선언하고 result[0] = 0, result[1] = sequence.length - 1 로 설정한다.

# 시작 인덱스 값을 저장할 start, 인덱스 사이의 합을 저장할 sum 를 선언한다.

# for 문의 루프 변수를 마지막 인덱스 end 로 설정하고 부분 수열의 합 sum 을 구한다.

# sum > k 인 경우, sum 에서 시작 인덱스 start 에 해당하는 값을 빼고 start 를 1 증가시킨다.

# sum = k 인 경우, 이전 인덱스 보다 현재 인덱스의 우선 순위가 높다면 배열 result 값을 갱신한다.

# 시작 인덱스와 마지막 인데스의 차이가 적을수록 우선 순위가 높다.

# result 를 리턴한다.

 

코드 구현

class Solution {
    public int[] solution(int[] sequence, int k) {
        int[] result = {0, sequence.length - 1};
        int start = 0;
        int sum = 0;
        
        for(int end = 0; end < sequence.length; end++) {
            sum = sum + sequence[end];
            
            while(sum > k) {
                sum = sum - sequence[start];
                start++;
            }
            
            if(sum == k) {
                if((end - start) < result[1] - result[0]) {
                    result[0] = start;
                    result[1] = end;
                }
            }
        }
        
        return result;
    }
}