[프로그래머스] Lv.2 연속된 부분 수열의 합 (Java)

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

프로그래머스

 

문제 설명

비내림차순으로 정렬된 수열이 주어질 때, 다음 조건을 만족하는 부분 수열을 찾으려고 합니다. 

- 기존 수열에서 임의의 두 인덱스의 원소와 그 사이의 원소를 모두 포함하는 부분 수열이어야 합니다.

- 부분 수열의 합은 k입니다.

- 합이 k인 부분 수열이 여러 개인 경우 길이가 짧은 수열을 찾습니다.

- 길이가 짧은 수열이 여러 개인 경우 앞쪽에 나오는 수열을 찾습니다.

 

수열을 나타내는 정수 배열 sequence와 부분 수열의 합을 나타내는 정수 k가 매개변수로 주어질 때, 위 조건을 만족하는 부분 수열의 시작 인덱스와 마지막 인덱스를 배열에 담아 return 하는 solution 함수를 완성해 주세요.

---

💡 아이디어

부분수열의 합을 매번 조사하면서 검사하기에는 무조건 이중이상의 반복문을 쓸 수밖에 없습니다.

따라서 다른 방법을 사용해야 하는데 부분수열의 왼쪽 끝지점과 오른쪽 끝지점을 움직이면서 부분수열의 합이 k가 되는 지점을 찾는 방식으로 진행하면 한 번의 반복문만 사용하기 때문에 시간 초과가 나지 않습니다.

 

📗 풀이과정

위의 1-6번 과정과 같이 처음 left:0, right:0에서 시작해 부분수열의 합이 k보다 작으면 right를 오른쪽으로 한 칸 옮기고, 

k보다 커진다면 left를 오른쪽으로 한 칸 옮겨 부분수열의 합을 줄입니다.

 

마침내 6번 처럼 부분수열의 합이 k인 지점을 만난다면 left와 right 값을 저장해 둡니다.

그런 뒤, 더 짧은 길이의 부분수열도 있을 수 있기 때문에 작업을 해 나갑니다.

마지막 index까지 모두 조사를 완료했는데 더 짧은 부분수열이면서 합이 k인 수열은 더 이상 나오지 않았기 때문에 

기존에 저장했던 left와 right값이 저장된 answer를 return 합니다.

---

풀이 과정에 따른 전체 코드

class Solution {
    public int[] solution(int[] sequence, int k) {
        int[] answer = {0,sequence.length-1};
        
        int sum=sequence[0];//부분수열의 합
        int left=0, right=0;
        while(true){
            if(sum<k){//부분수열 합이 k보다 작으면 right 하나 늘려줌
                if(right==sequence.length-1) break;//끝까지 갔다면 종료.
                right++;
                sum+=sequence[right];
                
            }else if(sum==k){//부분수열의 합이 k일때
                if(right-left<answer[1]-answer[0]){//더 작은 길이 저장.
                    answer[0]=left;
                    answer[1]=right;
                }
                //둘다 끝지점에 도달하면 종료
                if(right==sequence.length-1 && left==sequence.length-1){
                    break;
                }else if(right==sequence.length-1){//오른쪽만 끝지점이면 left 오른쪽으로 옮김
                    sum-=sequence[left];
                    left++;
                }else{//오른쪽으로 더 조사할 수 있으면 조사하기
                    right++;
                    sum+=sequence[right];
                }
            }else{//부분수열의 합이 k보다 크면 left값 오른쪽으로 옮김.
                sum-=sequence[left];
                left++;
            }
        }
        
        return answer;
    }
}