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

문제

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

프로그래머스

 

---

 

문제 개요

이번 문제는 비내림차순(오름차순)으로 정렬된 수열에서 특정 조건을 만족하는 부분 수열을 찾아내는 문제입니다. 수열과 목표 합 k가 주어졌을 때, 다음과 같은 조건을 만족하는 부분 수열의 시작과 끝 인덱스를 찾아야 합니다.

 

문제 접근 방법

문제를 해결하기 위해 투 포인터 알고리즘을 사용하였습니다. 이 방법은 효율적인 연속 부분 수열 탐색에 적합하며, 특정 조건을 만족하는 수열의 구간을 빠르게 탐색할 수 있습니다. 다음은 문제를 해결하기 위한 접근 방식입니다.

1. 포인터 초기화:
   • start와 end 두 포인터를 초기화합니다. start는 현재 탐색하는 부분 수열의 시작 인덱스를, end는 끝 인덱스를 나타냅니다.
   • sum 변수는 현재 부분 수열의 합을 저장합니다.
   • minSize는 최소 길이를 저장하며, 초기값으로 Integer.MAX_VALUE를 사용합니다.
2. 부분 수열의 탐색:
   • end 포인터를 증가시키며 수열의 끝까지 탐색합니다.
   • sum에 sequence[end] 값을 더합니다.
3. 합이 k 이상일 때 처리:
   • 합이 k 이상이면 sum이 k인지 확인합니다.
   • 합이 k와 같을 때, 현재 부분 수열의 길이가 minSize보다 작으면, answer 배열에 start와 end - 1 값을 저장하고 minSize를 갱신합니다.
   • sum에서 sequence[start] 값을 빼고 start 포인터를 증가시켜 부분 수열을 줄입니다.

 

import java.util.*;

class Solution {
    public int[] solution(int[] sequence, int k) {
        int start = 0, end = 0, sum = 0;
        int minSize = Integer.MAX_VALUE;
        int[] answer = new int[2];

        while (end < sequence.length) {
            sum += sequence[end++];
            
            while (sum >= k) {
                if (sum == k && (end - start) < minSize) {
                    minSize = end - start;
                    answer[0] = start;
                    answer[1] = end - 1;
                }
                sum -= sequence[start++];
            }
        }

        return answer;
    }
}