Lv.2 : 연속된 부분 수열의 합

👉 문제링크

프로그래머스

---

---

🔸 문제 분석 🔸

• 비내림차순 수열의 부분 수열 중 합이 k가 되는 가장 짧은 부분 수열의 시작과 끝 인덱스를 반환한다.
• 같은 길이가 여러개 나오는 경우 먼저 나온 부분 수열을 사용한다.

🔸 문제 풀이 🔸

• 인덱스를 이동하며 부분 수열의 합을 계산하는 문제이므로, 투포인터로 풀이한다.
  • 두 인덱스 left와 right를 지정하고, k보다 작으면 right + 1, k보다 크다면 left + 1로 이동한다.
  • 인덱스가 변할 때 부분 수열의 합도 변경하며 계산한다.
  • 부분 수열의 합이 k와 같아진다면, 길이가 최소일 경우 인덱스를 저장한다.

---

🔸 코드 🔸

class Solution {
    public int[] solution(int[] sequence, int k) {

        int[] answer = new int[2];
        int min = Integer.MAX_VALUE;

        int left = 0;
        int right = 0;
        int window = sequence[0];

        while (left <= right && right < sequence.length) {
            if (window == k) {

                if (min > right-left) {
                    min = right-left;
                    answer[0] = left;
                    answer[1] = right;
                }

                window -= sequence[left++];
                if (++right < sequence.length)
                    window += sequence[right];
            } else if (window > k) {
                window -= sequence[left++];
            } else {
                if (++right < sequence.length)
                    window += sequence[right];
            }
        }
        return answer;
    }
}

🔸 코드 해석 🔸

• 부분 수열의 좌우 인덱스를 left, right에 저장하고 합을 window에 저장한다.
• int 변수 min에 부분 수열의 합이 k일때의 길이를 저장하고, 최소값을 찾아간다.
• left가 right보다 커지거나, right가 수열의 길이를 벗어나면 더이상 해당하는 부분 수열이 없는 것이므로 계산을 종료한다.
  • 부분 수열의 합이 k가 됐다면, min보다 짧은 경우 정답 인덱스를 갱신하고, left와 right를 +1 한다.
  • 부분 수열의 합이 k보다 크다면, window에서 기존 left 인덱스 값을 빼고, left를 +1 한다.
  • 부분 수열의 합이 k보다 작다면, right를 +1하고, widnow에 right 인덱스 값을 더한다.
• 저장한 인덱스 배열 answer를 반환한다.

---

🔸 end 🔸

• 부분 수열의 합을 확인하며 인덱스를 진행하는 방식이 전형적인 투포인터 방식이라 간단히 풀이할 수 있었다.