프로그래머스 2단계 : 연속된 부분 수열의 합 (Java 자바)

 

프로그래머스

 

문제 설명

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

• 기존 수열에서 임의의 두 인덱스의 원소와 그 사이의 원소를 모두 포함하는 부분 수열이어야 합니다.
• 부분 수열의 합은 k입니다.
• 합이 k인 부분 수열이 여러 개인 경우 길이가 짧은 수열을 찾습니다.
• 길이가 짧은 수열이 여러 개인 경우 앞쪽(시작 인덱스가 작은)에 나오는 수열을 찾습니다.

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

 

 

 

제한사항

 

• 5 ≤ sequence의 길이 ≤ 1,000,000
• 1 ≤ sequence의 원소 ≤ 1,000
• sequence는 비내림차순으로 정렬되어 있습니다.
• 5 ≤ k ≤ 1,000,000,000
• k는 항상 sequence의 부분 수열로 만들 수 있는 값입니다.

 

입출력 예

 

 

 

 

풀이

 

주어진 수열에서 합이 k가 되는 부분 수열을 찾는데, 길이가 짧고 시작 인덱스가 낮은 부분 수열을 반환합니다.

주어진 조건을 만족하는 부분 수열을 효율적으로 찾아내고, 해당 부분 수열의 시작과 끝 인덱스를 반환합니다.

 

class Solution {
    public int[] solution(int[] sequence, int k) {
        int N = sequence.length; // 수열의 길이
        int left = 0, right = N; // 부분 수열의 시작과 끝 인덱스를 초기화
        int sum = 0; // 부분 수열의 합을 나타내는 변수

        for (int L = 0, R = 0; L < N; L++) { // L은 부분 수열의 시작 인덱스, R은 부분 수열의 끝 인덱스를 나타냄
            while (R < N && sum < k) { // 부분 수열의 합이 k 미만이면 R을 증가시키며 합을 구함
                sum += sequence[R++];
            }

            if (sum == k) { // 합이 k와 같으면
                int range = R - L - 1; // 부분 수열의 길이를 구함
                if ((right - left) > range) { // 이전에 찾은 부분 수열보다 길이가 짧다면
                    left = L; // 시작 인덱스를 갱신
                    right = R - 1; // 끝 인덱스를 갱신
                }
            }

            sum -= sequence[L]; // 부분 수열의 합에서 L 위치의 값을 빼고 다음 부분 수열을 확인하기 위해 L을 증가
        }

        int[] answer = { left, right }; // 결과로 반환할 시작과 끝 인덱스를 배열로 생성

        return answer; // 결과 배열을 반환
    }
}