프로그래머스 연속된 부분 수열의 합 자바 풀이

문제 링크

문제 요약

비내림차순으로 정렬된 수열 sequence와 목표 합 k가 주어진다
합이 k인 연속 부분 수열 중 길이가 가장 짧은 것을 찾는다
길이가 같으면 시작 인덱스가 더 작은 쪽을 찾는다

문제 풀이

처음에는 모든 구간의 합을 완전탐색으로 구해서 k와 비교하면 되겠다고 생각했다.

하지만 이 방식은 비효율적이다.

sequence의 길이가 최대 1,000,000인데, 모든 구간을 다 확인하면 경우의 수가 n^2에 가까워져서 10^12를 넘어간다.

이 문제의 핵심은 수열이 이미 정렬돼 있어서, 구간에 원소를 더할수록 합이 커지고 뺄수록 작아진다는 점이다.

그래서 투 포인터로 윈도우를 유지하면서, 합이 k보다 커지면 왼쪽 끝을 줄이고, k와 같아지면 그때 길이를 비교하면 된다.

오른쪽 끝을 한 칸씩 늘려가면서 합에 더하고, 합이 k를 넘으면 왼쪽 끝을 줄여가며 합에서 뺀다.

합이 정확히 k가 되는 순간마다 현재 구간의 길이가 지금까지 찾은 답보다 짧으면 답을 갱신한다.

왼쪽과 오른쪽 포인터가 각각 한 번씩만 움직이기 때문에 전체 시간 복잡도는 O(n)이다.

최종 코드

java

class Solution {
    public int[] solution(int[] sequence, int k) {
        int n = sequence.length;
        
        int[] answer = new int[]{0, n-1}; // 일단 전체 구간을 기본 답으로 둔다
        
        int s = 0; // 윈도우의 왼쪽 끝
        int sum = 0;
        
        for(int e = 0; e < n; e++) { // 윈도우의 오른쪽 끝을 한 칸씩 늘려간다
            sum += sequence[e];
            
            while(sum > k && s <= e) { // 합이 k를 넘으면 왼쪽 끝을 줄여서 합을 줄인다
                sum -= sequence[s];
                s++;
            }
            
            if(sum == k) {
                if(e - s < answer[1] - answer[0]) { // 더 짧은 구간을 찾으면 답을 갱신
                    answer[0] = s;
                    answer[1] = e;
                }
            }
        }
        
        return answer;
    }
}

연속된 부분 수열의 합

문제 요약

문제 풀이

최종 코드

함께 읽으면 좋은 글

택배상자

롤케이크 자르기

할인 행사

숫자 변환하기