[Programmers] 연속된 부분 수열의 합 (Lv.2) 2023/7/9

문제 제목	정답률	난이도
연속된 부분 수열의 합	49%	Lv.2

프로그래머스

 

문제요약

오름차순으로 정렬된 수열과 부분수열의 합이 주어질 때, 다음 조건을 만족하는 부분수열은 존재한다. 이때, 최소 길이를 가지는 부분수열의 인덱스를 반환하여라.

조건 1) 부분수열은 두 인덱스의 원소와 그 사이의 원소를 모두 포함한다.

조건 2) 부분수열이 여러 개인 경우 길이가 짧은 수열을 반환한다.

조건 3) 길이가 짧은 수열이 여러 개인 경우 앞쪽 인덱스의 부분수열이 최소 부분수열이다.

 

 

생각할 것

우선, '연속된'과 부분수열 단어를 보고 투 포인터를 떠올려야 한다.

처음 시작을 맨 앞으로 하면 두 포인터는 증가해야 한다.

수열의 합을 늘리려면, 인덱스 범위를 증가시켜야 하고, 합을 줄이려면 인덱스 범위를 감소시켜야 한다.

 

- 수열의 합 증가(인덱스 범위 증가)

• startidx 감소, 혹은 endidx 증가

- 수열의 합 감소(인덱스 범위 감소)

• startidx 증가, 혹은 endidx 감소

 

풀이

Step1. 합이 k보다 큰 경우

• 범위 감소(startidx 증가)

Step2. 합이 k보다 작은 경우

• 범위 증가(endidx 증가)

Step3. 합이 k와 같은 경우

• 기존의 답의 범위와 비교하여, 기존 범위보다 작은 경우 업데이트(크거나 같으면 현상유지) 
• startidx 증가시켜 새로운 답 탐색

 

코드

class Solution {
    public int[] solution(int[] sequence, int k) {
        int[] answer = new int[2];
        // 길이 순서로 탐색
        int startidx=0;
        int endidx=0;
        int sum=0;
        int min_range=sequence.length;
        while(startidx<=endidx){
            if(sum<k){
                if (endidx>=sequence.length){
                    break;
                }
                sum+=sequence[endidx++];
            }else{//sum>k
                sum-=sequence[startidx++];
            }
            if (sum==k){ //최소와 비교하여 업데이트
                if (min_range>endidx-startidx-1){
                    answer[0] = startidx;
                    answer[1] = endidx-1; 
                    min_range=answer[1]-answer[0];
                }
            }
        }
        return answer;
    }
}