[프로그래머스] 연속된 부분 수열의 합 - Java

문제 링크

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

문제 설명

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

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

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

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

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

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

제한사항

입출력 예

알고리즘: 누적합, 이분 탐색

풀이

1. 먼저 연속된 부분 수열이기 때문에 누적합을 구해준다.
2. 누적합 배열 요소를 하나씩 체크한다. (누적합 - k == 0)이면 0~i 부분 수열의 합이 k라는 의미이기 때문에 answer을 check해서 업데이트해 주고,
   (누적합 - k > 0)이면 누적합 배열에서 0~i-1 범위에 (누적합 - k)값이 존재하는지 찾아본다. 찾을 때는 이분 탐색을 이용한다. (sequence가 오름차순이면 누적합도 오름차순이다.)

소스 코드

class Solution {
    static int[] sum; //누적합 배열
    public int[] solution(int[] sequence, int k) {
        int[] answer = {0, sequence.length};
        sum = new int[sequence.length];
        for(int i=0; i<sequence.length; i++) {
            if(i==0) sum[i] = sequence[i];
            else sum[i] = sum[i-1] + sequence[i];
        }
        for(int i=0; i<sum.length; i++) {
            int search_value = sum[i] - k;
            if(search_value == 0) update_answer(0, i, answer);
            else if(search_value > 0) {
                int s_ind = binary_search(search_value, i-1);
                if(s_ind != -1) update_answer(s_ind + 1, i, answer);
            }
        }
        return answer;
    }
    static int binary_search(int value, int max) {
        int min = 0;
        while(min<=max) {
            int mid = (min + max) / 2;
            if(sum[mid] == value) return mid;
            if(sum[mid] < value) min = mid + 1;
            else if(sum[mid] > value) max = mid - 1;
        }
        return -1;
    }
    static void update_answer(int s, int e, int[] answer) {
        boolean change = false;
        if((e - s) < (answer[1] - answer[0])) change = true;
        else if(((e - s) == (answer[1] - answer[0])) && (s < answer[0])) change = true;
        if(change) {
            answer[0] = s;
            answer[1] = e;
        }
    }
}