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

문제

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

프로그래머스

 

---

첫번째 코드 - 시간 초과(테스트 케이스 10~16, 20~24)

class Solution {
    public static int[] solution(int[] sequence, int k) {
        int[] answer = {-1, -1}; // 초기화 시 비정상 값을 사용

        for (int i = 0; i < sequence.length; i++) {
            int sum = sequence[i];

            if (sum == k) { // 첫 번째 값이 k인 경우 처리
                if (answer[0] == -1 || (answer[1] - answer[0] > 0)) {
                    answer[0] = i;
                    answer[1] = i;
                }
                break;
            }

            for (int j = i + 1; j < sequence.length; j++) {
                sum += sequence[j];

                if (sum == k) { // sum이 k와 같아질 때까지 값을 더한 후 처리
                    if (answer[0] == -1 || (answer[1] - answer[0] > j - i)) {
                        answer[0] = i;
                        answer[1] = j;
                    }
                    break;
                } else if (sum > k) { // 더 이상 sum이 커지면 반복 종료
                    break;
                }
            }
        }

        return answer;
    }
}

 

 

투 포인터 알고리즘 사용

package week18.baek;

public class P178870 {
    public static int[] solution(int[] sequence, int k) {
        int left = 0, right = 0;
        int sum = sequence[0];  // 초기 합
        int[] answer = {-1, -1}; // 답을 저장할 배열
        int minLength = Integer.MAX_VALUE;  // 최소 길이를 추적

        while (right < sequence.length) {

            if (sum == k) {
                // 최소 길이보다 작으면 answer 업데이트
                if (right - left < minLength) {
                    minLength = right - left;
                    answer[0] = left;
                    answer[1] = right;
                }
                // 다음 쌍을 찾기 위해 왼쪽 포인터 이동
                sum -= sequence[left];
                left++;
            }
            else if (sum < k) {
                // 부분 합이 k보다 작을 때 오른쪽 포인터 이동
                right++;
                if (right < sequence.length) {
                    sum += sequence[right];
                }
            } 
            else {
                // 부분 합이 k보다 클 때 왼쪽 포인터 이동
                sum -= sequence[left];
                left++;
            }
        }

        return answer;
    }
    public static void main(String[] args) {
        int[] sequence = {2, 2, 2, 2, 2};
        System.out.println(solution(sequence, 6));
    }
}