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

문제를 읽고 완전 탐색은 인풋값이 크기 때문에 당연히 시간 초과가 난다고 생각해서 배제했다.

부분 수열 문제에서 O(N) 로직을 가지는 건 투포인터와 슬라이딩 윈도우인데, 이번 문제는 정렬되어 있고,

부분 수열의 길이가 가변적이니 투포인터를 사용했고

문제 조건에 맞게 저번 카카오 문제에서 썼던 Comparator를 사용하여 정렬하고 값을 리턴했다.

오랜만에 투포인터를 써서 더듬거리며 풀었지만 꽤 재미있었다.

---

최종 코드

import java.util.*;
class Solution {
    public int[] solution(int[] sequence, int k) {
        int[] answer = new int[2];
        List<int[]> list = new ArrayList<>();
        
        int start = 0;
        int end = 0;
        int sum = 0;
        
        while(start < sequence.length) {
            if(sum > k || end == sequence.length) {
                sum -= sequence[start++];
            } else {
                sum += sequence[end++];
            }
            
            if(sum == k) {
                list.add(new int[]{start, end - 1});
            }
        }
        
        list.sort((o1, o2) -> {
            int size1 = o1[1] - o1[0];
            int size2 = o2[1] - o2[0];
            if(size1 == size2) {
                return o1[0] - o2[0];
            } else {
                return size1 - size2;
            }
        });
        
        answer = list.get(0);
        return answer;
    }
}