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

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

프로그래머스

 

연속된 부분 수열의 합 문제

오름차순으로 정렬된 수열에서 조건에 맞는 부분수열의 시작, 끝 인덱스를 찾는 문제

 

#사용 알고리즘

투포인터(two pointers)

📌문제 접근 포인트

1. 오름차순으로 정렬된 수열에서 연속된 부분 수열의 합이 K가 되는 수열을 찾기 위해서는 투포인터를 사용하여 찾아나가면 된다.

2. 왼쪽과 오른쪽이 같은 지점에서 시작하여 K보다 작으면 오른쪽을, K보다 크면 왼쪽을 늘려가는 식으로 찾는다. 여기서 길이가 짧은 수열이 여러 개 일 경우 시작 인덱스가 작은 수열을 반환해야하므로 거리를 저장하여 비교할 수 있도록 구현한다.

3. 100만의 범위에서 무작정 for문을 이용한 합을 반복해서 구해줄 경우 시간 초과가 될 수 있다. 그렇기에 최초 S 값에서 인덱스를 알고 있으므로 오른쪽에서 늘릴 경우 S에 +를, 왼쪽을 늘릴 경우 S에 -를 하면 연산 수를 줄일 수 있다.

반응형

⚙ 내가 푼 정답 코드

import java.util.*;

class Solution {
    public int[] solution(int[] sequence, int k) {
        int[] result = new int[2];
        int n = sequence.length;
        int left = 0;
        int right = 0;
        int d = n+1;
        int S = sequence[0]; // 시작 S 값
        while (left <= right && right < n){
            if (S < k){ // 작으면
                right++; // 오른쪽 늘리고
                if (right == n){
                    break;
                }
                S += sequence[right]; // 합 증가
            }
            else if(S > k){ // 크면
                S -= sequence[left]; // 왼쪽 줄이고
                left++; // 왼쪽 증가
            }
            else{ // 값이 일치할 때
                if (d > right - left + 1){ // 기존보다 거리가 작을 때 수행
                    d = right - left + 1;
                    result[0] = left;
                    result[1] = right;
                }
                S -= sequence[left]; // 크기를 줄여야하므로 왼쪽을 이동
                left++;         
            }
        }
        
        return result;
    }
}