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

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

프로그래머스

 

시도 했던 방법

 처음엔 단순하게 배열로 풀었는데, 몇몇 테스트 케이스에서 시간초과가 떴다. 최악의 경우, (1000000)^2의 순회를 하기 때문이다.

정렬된 배열이 주어지므로 바이너리 서치 트리로 해결해보려고 이런 저런 시도를 해보다가 결국 시간 내에 시간초과를 해결하지 못 했는데, 힌트를 보고 투포인터로 해결해보았다.

 

 

작성한 코드 1 (완전 탐색) (시간 초과)

class Solution {
    public int[] solution(int[] sequence, int k) {
        int[] answer = {0,0};
        int minLength = sequence.length;
        
        //왼쪽부터 완전 탐색
        for (int i = 0; i < sequence.length; i++) {

            if (sequence[i] > k) break;
            
            if (sequence[i] == k) {
                answer[0] = i;
                answer[1] = i;
                break;
            }
            
            int length = 0;

            int sum = sequence[i];

            for (int j = i+1; ; j++) {

                length++;
                if (j >= sequence.length) break;

                sum += sequence[j];

                if (sum == k && length < minLength) {
                    answer[0] = i;
                    answer[1] = j;
                    minLength = length;
                }
                else if (sum > k) break;
            }
        }

        return answer;
    }
}

 

 

문제 풀이

투포인터 알고리즘 사용

1. 왼쪽, 오른쪽 인덱스, 부분 합계 변수를 선언

2. 부분 합계가 k보다 작거나 같으면, 오른쪽 인덱스 증가 (sum += sequence[right])

3. 부분 합계가 k보다 크거나 같으면, 왼쪽 인덱스 증가 (sum -= sequence[left])

4. 부분 합계가 k와 같으면, 리스트에 저장

5. 리스트에서 길이가 가장 짧은 수열 리턴

 

 

작성한 코드 2 (투 포인터) (정답)

import java.util.*;

class Solution {
    public int[] solution(int[] sequence, int k) {

        // 투포인터
        int leftIdx = 0;
        int rightIdx = 0;

        int length = sequence.length;
        int sum = sequence[0];

        List<int[]> list = new ArrayList<>();

        while (leftIdx < length && rightIdx < length) {

            if (sum == k) {
                list.add(new int[]{leftIdx, rightIdx});
            }

            if (sum <= k) {
                rightIdx++;
                if (rightIdx < length) {
                    sum += sequence[rightIdx];
                }
            }
            else {
                if (leftIdx < length) {
                    sum -= sequence[leftIdx];
                }
                leftIdx++;
            }
        }


        return list.stream()
                .min(Comparator.comparingInt(arr -> arr[1] - arr[0]))
                .orElseThrow();
    }
}