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

1. 문제

연속된 부분 수열의 합

2. 개요

비내림차순으로 정렬된 수열이 주어진다. 이 수열 안에서 밑의 조건을 만족하는 연속된 부분 수열을 찾으려고 한다.

• 연속된 부분 수열이어야 한다.
• 부분 수열의 모든 원소들의 합이 k여야 한다.
• 합이 k인 부분 수열이 여럿일 경우 가장 짧은 부분 수열을 찾는다.
• 길이가 가장 짧은 부분 수열이 여럿일 경우 가장 앞의 부분 수열을 찾는다.

찾아낸 부분 수열의 시작 인덱스와 끝 인덱스를 반환하는 문제.

3. 풀이 및 코드

3-1. 풀이

먼저 누적합 배열을 만들어둔다.

x <= y일 때, x부터 y까지의 부분 수열의 합은 y까지의 누적합 - x까지의 누적합으로 구할 수 있다.

l포인터와 r포인터를 만들고 해당 구역의 합을 조건과 비교, 포인터를 이동시켜가면서 답을 구할 수 있다.

3-2. C#

using System;

public class Solution {
    public int[] solution(int[] sequence, int k) {
        int[] answer = new int[] { 0, 10000001 };

        int[] sums = new int[sequence.Length + 1];

        for (int i = 1; i < sequence.Length + 1; i++)
            sums[i] = sums[i - 1] + sequence[i - 1];

        int l = 0, r = 0;

        while (l <= r && r < sums.Length)
        {
            if (sums[r] - sums[l] == k)
            {
                if (r - l < answer[1] - answer[0] + 1)
                {
                    answer[0] = l;
                    answer[1] = r - 1;
                }
                l++;
                r++;
            }

            else if (sums[r] - sums[l] < k)
                r++;

            else
                l++;
        }

        return answer;
    }
}