[JAVA] 연속된 부분 수열의 합 - 프로그래머스 LV2

해당 문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/178870

해결방법

문제의 제한사항이다. 배열의 크기가 1,000,000까지 될 수 있기다 O(n^2)이상의 시간복잡도 알고리즘을 사용하면 안된다고 판단했다.
투 포인트라는 알고리즘을 사용했는데 자세한 설명은 여기에서 도움 많이 받았다.

1. 연속된 부분 수열의 시작과 끝을 0으로 설정한다.
2. 연속된 부분 수열의 합이 k보다 크다면 합에 시작값을 빼고 시작인덱스를 증가 시켜준다.
3. 연속된 부분 수열의 합이 k보다 작다면 끝 인덱스를 증가시키고 합에 증가된 끝값을 더해준다.
4. 연속된 부분 수열의 합이 k와 같다면 기존에 저장된 연속된 부분 수열의 크기와 비교 후 작을 때 새로운 연속된 부분 수열로 저장시키고 끝 인덱스를 증가시키고 합에 증가된 끝값을 더해준다.
5. 두 포인터가 배열 끝에 도달하면 종료.

생각할 점

투 포인터라는 알고리즘을 이번 기회에 알 게 되었다. 혼자서 풀다보니 시간초과로 풀리지 않아서 해답을 보게되었는데 알고리즘 공부할 때 시간복잡도를 따져볼 수 있도록 연습을 많이 해야겠다.

소스 코드

public static int[] solution(int[] sequence, int k) {
        int[] answer = {};

        int max = sequence.length - 1;
        int sum = sequence[0];
        int start = 0;
        int end = 0;
        int size = Integer.MAX_VALUE;
        while (true) {
            if (sum == k) {
                int currentSize = end - start + 1;
                if (size > currentSize) {
                    size = currentSize;
                    answer = new int[]{start, end};
                }
            }
            if (end == max && start == max) {
                break;
            }
            if (sum < k && end < max) {
                end++;
                sum += sequence[end];
            } else {
                sum -= sequence[start];
                start++;
            }
        }
        return answer;
    }

참고사이트

https://butter-shower.tistory.com/226