프로그래머스 스쿨(Java - Lv.2) - 연속된 부분 수열의 합[투포인터/윈도우슬라이드 합산방식고찰]

문제

 

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

프로그래머스

 

 

해답

 

class Solution {
    public int[] solution(int[] sequence, int k) {
        int[] answer = {};
        
        int p1 = 0;
        int p2 = 0;
        int sum = sequence[0];
        int length = Integer.MAX_VALUE;
        
        while(p2<sequence.length){
            if(sum==k){ //합과 같을경우
                if((p2-p1)<length){ //길이가 더 짧을경우 답으로 처리
                    answer = new int[]{p1,p2};
                    length=p2-p1;
                }
                
                if(p1<p2){ //숫자가 여러개일때
                    sum-=sequence[p1++];
                }
                else{ //숫자가 같을때
                    sum = sequence[p1++];
                    p2++;
                }
            }else{
                if(sum>k){ //합이 더클때
                    if(p1<p2){ //숫자가 여러개일때
                        sum-=sequence[p1++];
                    }
                    else{ //숫자가 같을때
                        sum = sequence[p1++];
                        p2++;
                    }    
                }else if(sum<k){ //합이 더 작을때
                    if(p2+1==sequence.length) return answer;
                    sum += sequence[++p2];
                }
            }
        }
        
        return answer;
    }
}

 

 

해설

 

투포인터와 윈도우슬라이드 2가지 개념을 사용한다는 문제는 맞다

 

다만 여기에서 투포인터를 옮길때마다 포인터의 시작과 끝값까지의 합을 매번 구하는 방식으로 했더니

 

시간초과를 맞게되었다.

 

의도로보아 이 문제는 일부러 투포인터의 구간이 무진장 길어지는 문제를 투어 시간 복잡도를

 

O(n^2*(n-1)/2) 까지 증가시킬 수 있는 문제로 만들어 사실상 O(n^2)로 만드는 문제로 바꾸어 버린다.

 

따라서 매번 새로운 계산이 아닌 숫자의 합산의 경우 포인터가 이동할경우 그 값을 가져와

 

앞포인터 전진의 경우 그 값을 빼주고, 뒤포인터 전진의 경우 새로 들어가는 값을 더해주는 방식으로 처리하니 시간에서도

 

문제없이 통과를 할 수 있게되었다.