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

🔗 연속된 부분 수열의 합

비내림차순으로 정렬된 수열에서 합이 k인 부분 수열을 찾는 문제이다. 부분 수열이 여러 개 있을 경우, 길이가 짧은 수열을 선택해야하며, 길이가 같은 부분 수열이 여러 개라면 앞쪽에 위치한 수열을 선택한다.

 

🥊 접근 방법 🥊

정답 코드를 참고했다 ㅠㅠ 투포인터가 부족한 것 같다.

 

1. 투포인터

left, right 두 개의 포인터를 사용해 부분 수열의 시작과 끝을 관리한다. right를 이동시키며 수열의 합 sum을 계산한다.

int left = 0;  // 수열의 시작이 될 부분
int right = 0;  // 수열의 끝이 될 부분
int len = sequence.length;
int sum = 0;

// right을 이동시키며 수열의 합 계산
for(int i=0; right<len; i++){
    sum += sequence[right];
    right++;
}

 

2. 조건 이동

sum이 k보다 커지면 left를 이동키면서 값을 sum에서 뺀다. sum이 k와 같아지면 현재 부분 수열이 조건을 만족하는지 확인한다. 이때, 길이가 짧은지 확인하고, 현재까지 찾은 부분 수열보다 짧다면 answer에 left와 right 값을 저장한다.

int min = sequence.length;
while(sum > k){  // sum이 k보다 커지면
    sum -= sequence[left];  // 값 뺀다
    left++;
}

if(sum == k){
    // 길이가 짧은 수열을 선택해야 함
    if(min > right-left){
        min = right-left;
        answer[0] = left;
        answer[1] = right;
    }
}

 

✨ 전체코드 ✨

• sequence : 수열을 나타내는 정수 배열
• k : 부분 수열의 합을 나타내는 정수

class Solution {
    public int[] solution(int[] sequence, int k) {
        int[] answer = new int[2];
        
        int left = 0;
        int right = 0;
        int len = sequence.length;
        int min = len;
        int sum = 0;
        
        for(int i=0; right<len; i++){
            sum += sequence[right];
            
            while(sum > k){
                sum -= sequence[left];
                left++;
            }
            
            if(sum == k){
                if(min > right-left){
                    min = right-left;
                    answer[0] = left;
                    answer[1] = right;
                }
            } right++;
        } return answer;
    }
}

 

🌀 성능

• 메모리 : 132 MB
• 시간 : 13.61 ms