[Programmers] 연속된 부분 수열의 합

[문제 링크]

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

프로그래머스

 

 

[풀이 과정]

Two Pointer문제입니다.

start와 end 인덱스 값을 주고 start와 end사이의 합을 sum으로 둡니다.

비내림차순으로 정렬되어 있기 때문에 sum이 구하려고 하는 값보다 작으면 

end idx 값을 올리고 sum이 구하려고 하는 값보다 크면 start idx 값을 올려값을 찾아간다.

 

[코드]

import java.util.*;

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

        while (end < n) {
            if (sum < k) {
                end++;
                if (end < n) {
                    sum += sequence[end];
                }
            } else if (sum > k) {
                sum -= sequence[start];
                start++;
            } else { // sum == k
                if (end - start < minLen) {
                    minLen = end - start;
                    answer[0] = start;
                    answer[1] = end;
                }
            
                // sum == k 여도 더 짧은 부분집합이 있을 수 있기 때문에
                // 계속 탐색
                sum -= sequence[start];
                start++;
            }
        }

        return answer;
    }
}

[회고]

two pointer 개념은 알고 있지만 생각이 나질 않아 풀이 과정을 보고 구현하였습니다.

아직 경험이 부족한 것 같습니다.

 

 

 

 

질문과 피드백은 언제나 환영입니다.

감사합니다.