투 포인터 (1) - 연속된 부분 수열의 합

문제

비내림차순으로 정렬된 수열이 주어질 때, 다음 조건을 만족하는 부분 수열을 찾으려고 합니다. 기존 수열에서 임의의 두 인덱스의 원소와 그 사이의 원소를 모두 포함하는 부분 수열이어야 합니다. 부분 수열의 합은 k입니다. 합이 k인 부분 수열이 여러 개인 경우 길이가 짧은 수열을 찾습니다. 길이가 짧은 수열이 여러 개인 경우 앞쪽(시작 인덱스가 작은)에 나오는 수열을 찾습니다. 수열을 나타내는 정수 배열 sequence와 부분 수열의 합을 나타내는 정수 k가 매개변수로 주어질 때, 위 조건을 만족하는 부분 수열의 시작 인덱스와 마지막 인덱스를 배열에 담아 return 하는 solution 함수를 완성해주세요. 이때 수열의 인덱스는 0부터 시작합니다.

 

 

조건

1. 합이 k인 수열이 여러 개일 경우 가장 짧은 수열을 찾습니다.

합이 k를 만족하는 여러 개의 수열 중 가장 짧은 수열을 찾아준다.

 

2. 길이가 짧은 수열이 여러 개인 경우 앞쪽(시작 인덱스가 작은)에 나오는 수열을 찾습니다.

k의 합을 만족하는 가장 짧은 길이의 수열이 여러 개일 경우, 인덱스가 작은 수열을 answer에 담아준다.

 

 

풀이

정말 간단하게 풀 수 있는 문제이다. 슬라이딩 윈도우의 개념에서 한 단계 업그레이드 된 동적인 슬라이딩 윈도우라고 생각하면 된다. 투 포인터란, 배열에서 인덱스를 지정해주는 두 개의 포인터를 이용하여 일정 조건에 맞게 조작할 수 있는 개념이다. 단, 위의 문제 같은 경우는 인덱스 사이의 원소를 모두 포함하는 부분수열의 합을 구하는 것이므로, 비내림차순으로 정렬되어있다는 말이 핵심이다.

class Solution {
        public static int[] solution(int[] sequence, int k) {
        int[] answer = new int[2];
        int start = 0;
        int end = 0;
        int leng = 1000000;
        int sum = sequence[0];
        while (start <= end) {
            if(sum == k){
                int Lleng = end - start;
                if(leng > Lleng){
                    leng = Lleng;
                    answer[0] = start;
                    answer[1] = end;
                }
                if(++end == sequence.length){
                    break;
                }
                sum += sequence[end];

            }
            else if(sum > k){
                sum -= sequence[start++];
            }
            else {
                if(++end == sequence.length){
                    break;
                }
                sum += sequence[end];
            }
        }
        return answer;
    }
}

 

먼저, 수열의 최대 길이는 1000000이라고 주어졌으므로, 길이의 최솟값을 계속 갱신해나가기 위하여 최대값으로 시작한다. 그 후, sum이라는 변수를 통해 합이 k와 같을 경우, 해당 인덱스의 거리가 짧다면 answer과 함께 전역적으로 선언한 최소 길이를 갱신해주고, 뒤에 나올 k와 같은 값을 대비하여 end를 하나 늘려준다.

그 이후로, sum이 k보다 작다면 end값을 늘리고, 포인터를 하나 이동시켜주고 k보다 크다면, start값을 하나 늘린 뒤, start값 만큼 sum에서 빼주면 sum이 계속 더해졌다가 빼졌다가를 반복하면서 정답을 갱신해 나갈 수 있다.

 

투 포인터에서 가장 중요한 것은 인덱스의 범위인데, 범위가 초과하는 것을 방지하기 위해 조건문과, 적절한 타이밍에 break를 걸어주는 것이 가장 중요하다.

if(++end == sequence.length){ break; }

 

나는 start와 end가 같을 때를 대비하여 <=로 처음에 걸어주었기 때문에 end값이 배열을 벗어날 수 있어 해당 조건문을 걸어주었다.