99클럽 코테 스터디 18일차 TIL 연속된 부분 수열의 합 - 자바(Java)

 

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

프로그래머스

 

보자마자 투포인터가 떠올랐다. 

배열에 위치를 가르키는 포인터를 두개 사용하여

왼쪽은 제일 처음 오른쪽도 0에서 시작하지만

목표하는 k가 되기 위하여 오른쪽 포인터를 옮겨가며 더해주다가 

k보다 커지면 왼쪽포인터를 이동하는 방식이다.

 

처음에 작성한 코드

 

class Solution {
    public int[] solution(int[] sequence, int k) {
        //투포인터
        int left = 0;
        int right = sequence.length - 1;
        int range = sequence.length; //최소 범위인지
        for(int tempLeft = 0; tempLeft < sequence.length; tempLeft++){//왼쪽 이 증가하면서 찾기
            int tempRight = tempLeft; //하나만 들어갈 수도
            int sum = 0;
            while(sum < k && tempRight < sequence.length){
                sum += sequence[tempRight++];
            }
            if(sum == k){
                if(right - left > tempRight - tempLeft - 1){
                    left = tempLeft;
                    right = tempRight - 1; //while문에서 수행후 1이 더해져 있기 때문
                }
            }
            
        }
        int[] answer = {left, right};
        return answer;
    }
}

 

sum과 오른쪽 포인터를 잘못 관리 했다는 것을 깨닫고 수정하였다.

 

그리고 문제에서 

 

길이가 짧은 수열이 여러 개인 경우 앞쪽(시작 인덱스가 작은)에 나오는 수열을 찾습니다.

 

 

라고 하였는데 

이를 구현하려고 조건문을 and로 더 넣을려다가

길이가 같을때는 그냥 넘어가게 두면 되는 간단한 방법이 있었다.

class Solution {
    public int[] solution(int[] sequence, int k) {
        //투포인터
        int left = 0;
        int right = sequence.length;
        int range = sequence.length; //최소 범위인지
        int sum = 0;
        for(int tempLeft = 0, tempRight = 0; tempLeft < sequence.length; tempLeft++){//왼쪽 이 증가하면서 찾기
            while(sum < k && tempRight < sequence.length){
                sum += sequence[tempRight++];
            }
            if(sum == k){
                if((right - left > tempRight - tempLeft - 1)){
                    left = tempLeft;
                    right = tempRight - 1; //while문에서 수행후 1이 더해져 있기 때문
                }
            }
            sum -= sequence[tempLeft];
            
        }
        int[] answer = {left, right};
        return answer;
    }
}