[Algorithm_Java] 연속된 부분 수열의 합 (Success)

프로그래머스

 

☕Language: Java

 

🚨 시간초과

class Solution {
    public int[] solution(int[] sequence, int k) {
        int[] answer = {0, 1000000};
        
        int i, j;
        for(i=0; i<sequence.length; i++){
            int sum=0;
            for(j=i; j<sequence.length; j++){
                if(sum==k){
                    if((j-i)<(answer[1]-answer[0])){
                        answer[0] = i;
                        answer[1] = j;
                        break;                        
                    }
                }
                if(sum<k){
                    sum += sequence[j];                    
                }
            }
        }
        return answer;
    }
}
 

이중 for문으로 인한 시간복잡도 향상(O(n))

 

😮 찾아본 풀이

⭐ 투 포인터

 

class Solution {
    int[] answer = {0, 1_000_000};
    
    public int[] solution(int[] sequence, int k) {
        
        int left = 0;
        int right = 0;
        
        int sum=0;
        while(right < sequence.length) {
            sum += sequence[right++];
            while(sum>k){
                sum -= sequence[left++];
            }
            
            if(sum==k){
                changeArr(left, right-1);
            }
        }
        return answer;
    }
    
    private void changeArr(int left, int right){
        if(right-left<answer[1]-answer[0]){
            answer[0] = left;
            answer[1] = right;
        }
    }
}
 

1. while(right < sequence.length)

    - sequence 길이 전까지 반복

2. sum += sequence[right++]

    - right pointer를 키워가며 sum에 덧셈

3. while(sum>k)

    - 단, sum이 k보다 커질 경우, left pointer를 키워가며 sum 뺄셈

4. if(sum==k)

    - changeArr(left, right-1)

        - 길이가 더 짧은 경우에만 answer에 입력하는 함수 작성

        - 단, right pointer의 경우 후위연산자로 1커졌으므로 조정 필요

        - 먼저 발견된 pointer를 출력하기 위해 if 조건문에 동등 연산자 제외

 

 

 

🔗 소스 코드
GitHub

 

📚 참고 자료

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