[Lv.2] 연속된 부분 수열의 합 [프로그래머스_코딩테스트] [투포인터, 슬라이딩 윈도우] [40분]

🔍 문제 요약

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

프로그래머스

오름차순으로 정렬된 수열을 sequence로 주어주고, 부분수열의 합이 k가 되는 구간을 찾는 문제. 구간이 여러개가 나온다면 구간의 길이가 짧으면서 시작 인덱스가 작은 것으로 결정한다.

🧠 나의 접근 방식과 시행착오

투포인터 문제로 접근은 올바르게 시작은 하였다. 다만 이 문제를 풀면서 끝 인덱스를 마지막 숫자의 인덱스로 접근을 했었다. (기존에 풀었던 다른 투포인터 문제를 해당 방향으로 풀면서 교차되는 케이스에 반복을 종료했던 케이스가 있었었다.) 그러나 해당 문제의 경우엔 그런식으로 풀게 되면 인덱스를 강제로 다시 초기화를 해주는 상태가 발생을 하게 되기도 한다. 결국 필자의 코드는 시간 초과와 런타임 에러를 뱉으면서 실패가 뜬 문제. 아래의 코드는 실패한 방법의 코드이다.

using System;
using System.Collections.Generic;

public class Solution
{
    /// <summary>
    /// 연속된 부분 수열의 합
    /// https://school.programmers.co.kr/learn/courses/30/lessons/178870
    /// </summary>
    public int[] solution(int[] sequence, int k)
    {
        // 오름차순으로 정렬된 수열 sequence
        // 부분수열의 합이 k인 인덱스 범위 구하기
        // 투포인터를 써서 작은 인덱스부터 올라가는 것 + 큰 인덱스에서 내려가는 것 으로 해서 합산 구하기
        int startIndex = 0;
        int lastIndex = sequence.Length - 1;
        
        // 부분 수열의 합을 구하기 위함
        var segment = new ArraySegment<int>(sequence, startIndex, sequence.Length);
        int sum = 0;
        // 목록 리스트
        var arrayList = new List<(int, int)>();

        while (true)
        {
            if (startIndex > lastIndex)
            {
                break;
            }

            sum = 0;
            var slice = segment.Slice(startIndex, lastIndex - startIndex + 1);

            foreach (var s in slice)
            {
                sum += s;
            }

            if (sum == k)
            {
                arrayList.Add((startIndex, lastIndex));
            }

            if (sequence[startIndex] > k)
            {
                startIndex--;
            }
            else if (sequence[lastIndex] > k)
            {
                lastIndex++;
            }
            else
            {
                // 서로 마주친 케이스. startIndex 증가시키고 lastIndex 다시 끝으로
                if (startIndex == lastIndex)
                {
                    startIndex++;
                    lastIndex = sequence.Length - 1;
                }
                else
                {
                    lastIndex--;
                }
            }
        }

        int minLength = int.MaxValue;
        int minStartIndex = int.MaxValue;
        var target = arrayList[0];

        foreach (var item in arrayList)
        {
            if (minStartIndex > item.Item1)
            {
                minStartIndex = item.Item1;
                target = item;
            }
            
            int diffIndex = item.Item2 - item.Item1;
            
            if (minLength > diffIndex)
            {
                minLength = diffIndex;
                target = item;
            }
        }
        
        int[] answer = new int[] {target.Item1, target.Item2};
        return answer;
    }
}

/// <summary>
/// C# 7.3
/// </summary>
internal class Program
{
    public static void Main(string[] args)
    {
        var sl = new Solution();
        var seq1 = new int[] { 1, 2, 3, 4, 5 };
        int k1 = 7;
        var seq2 = new int[] { 1, 1, 1, 2, 3, 4, 5 };
        int k2 = 5;
        var seq3 = new int[] { 2, 2, 2, 2, 2 };
        int k3 = 6;

        var res1 = sl.solution(seq1, k1);
        var res2 = sl.solution(seq2, k2);
        var res3 = sl.solution(seq3, k3);

        
        Console.WriteLine("{0} {1}", res1[0], res1[1]);
        Console.WriteLine("{0} {1}", res2[0], res2[1]);
        Console.WriteLine("{0} {1}", res3[0], res3[1]);
    }
}

 

✅ 풀이 코드

해당 문제는 start, end를 가장 작은 곳부터 시작해서 1씩 키워나가는 방식으로 슬라이딩 윈도우 방식으로 접근을 해야 한다. 그렇게 접근하는 기준은 아래와 같이 고려해서 판단내리면 된다.

 

추가로 해당 문제를 풀 때 영역의 합을 구하는 데에 필자가 썼었듯이 ArraySegment와 같은 것을 쓸 필요가 없어진다. 영역을 정할 때 해당 값을 빼주고 더해주면서 영역을 조절해 가면 된다. (ArraySegment를 반복에 추가하게 되면 시간 복잡도가 더 커지게 됨)

또 결과의 목록을 리스트에 저장하는 것까지도 필요 없이 풀이처럼 While 문에서 인덱스 간의 연산을 통해서 최소의 영역의 구간을 구할 수 있다. 그렇게 해서 반복은 end 인덱스가 sequence의 길이에 같아지는 경우 빠져나오게 된다. (따로 break을 걸고 나올 부분이 없음. 특정 조건을 통해서 구간을 전부 체크는 하긴 해야 할 것으로 보인다)

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

        while (end < sequence.Length) {
            if (sum < k) {
                end++;
                if (end < sequence.Length) sum += sequence[end];
            }
            else if (sum > k) {
                sum -= sequence[start];
                start++;
            }
            else {
                if (end - start < minLength) {
                    minLength = end - start;
                    answer[0] = start;
                    answer[1] = end;
                }
                sum -= sequence[start];
                start++;
            }
        }

        return answer;
    }
}

 

🔄 정리

선입견이 생길수 있었던 투포인터의 로직에서 기억해야할 기준을 명확히 세우고 그것을 토대로 풀이를 해야 할 것이다.