자바 - 프로그래머스 / 연속된 부분 수열의 합

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

프로그래머스

LV 2

 

구현 방법

5 ≤ sequence의 길이 ≤ 1,000,000

이므로 이중 포문 돌리면 런타임 에러 뜬다 이럴 때 쓰는 방법이 바로 투 포인터 알고리즘!  O(n)으로 가능하다. 

 

투 포인터 알고리즘을 사용해서 시작 부분, 끝 부분 두가지 포인터를 만들어서 원하는 연속된 합에 부합할때 까지 포인터를 움직이는 방법으로 구현했다. 원하는 값보다 작은 경우 끝 부분 포인터를 움직혀 합을 크게 하고, 원하는 값보다 커진 경우 시작 부분을 움직여 합을 줄이게 한다.

 

주의 할 점은 인덱스 범위를 체크해서 범위가 작은걸로 값을 업데이트 시켜야 한다.

 

코드

class Solution {
  
    public int[] solution(int[] sequence, int k) {
        int[] answer = new int[2];
        answer[0] = 0;
        answer[1] = sequence.length - 1;
        
        int start = 0;
        int end = 0;
        int sum = 0;
        
        while(start < sequence.length) {
            if(sum > k || end == sequence.length) {
                sum -= sequence[start];
                start++;
            } else {
                sum += sequence[end];
                end++;
            }
            
            if (sum == k) {
                //인덱스 범위 체크
                if(answer[1] - answer[0] > end - start - 1) {
                    answer[0] = start;
                    answer[1] = end - 1;
                } 
            }
        }
        
        return answer;
    }
}

 

느낀 점

개열받게 테스트 케이스 딱 하나 실패 떠서 오류 잡는다고 오래 걸린 문제...

오류 뜬 이유는 인덱스 범위 체크에서 범위가 작은 경우 확인하고, 범위가 같은 경우를 한번 더 확인해서 범위가 같은 경우는 break문으로 while문 빠져 나가서 생긴 오류 였다. 이렇게 하면 같은 범위, 같은 범위, 더 작은 범위 일 경우 더 작은 범위로 못가서 생기게 된다. 어휴~ 

 

그래도 투 포인터 알고리즘 배워서 유익했다^^

투 포인터 몇 문제 더 풀고 슬라이딩 윈도우 문제까지 풀어볼 계획이다.

 

참고 블로그

https://hongjuzzang.github.io/cs/two_pointers/

[java] 투 포인터 알고리즘