C# 연속된 부분 수열의 합 - 부분 합 투 포인터 / 프로그래머스 [Lv.2]

출처: 프로그래머스 코딩 테스트 연습
https://school.programmers.co.kr/learn/courses/30/lessons/178870

 

 

1차 시도

public int[] solution(int[] sequence, int k) 
{
    int start = 0;
    int end = 0;

    int minLength = int.MaxValue;
    int currentSum = 0;
    for(int i = 0; i < sequence.Length; ++i)
    {
        currentSum = 0;

        int maxOffset = minLength > sequence.Length - i ? sequence.Length - i : minLength;
        for(int offset = 0; offset < maxOffset; ++offset)
        {
            currentSum += sequence[i + offset];
            if(currentSum == k)
            {
                if(offset + 1 < minLength)
                {
                    minLength = offset + 1;
                    start = i;
                    end = i + offset;
                }
            }
            else if(currentSum > k)
            {
                break;
            }
        }
    }

    return new int[2] { start, end };
}

 

기존 수열에서 임의의 두 인덱스의 원소와 그 사이의 원소를 모두 포함하는 부분 수열이어야 합니다.

부분 수열의 합은 k입니다.

 - 순회하면서 합을 구하고, 같으면 부분수열이 될 수 있고 값을 무시한다.

 

합이 k인 부분 수열이 여러 개인 경우 길이가 짧은 수열을 찾습니다.

길이가 짧은 수열이 여러 개인 경우 앞쪽(시작 인덱스가 작은)에 나오는 수열을 찾습니다.

 - 부분 수열의 최소 길이를 관리해서, 앞에서부터 탐색할 때 작을 때만 교체해주면 된다. 

 

언제나 완전탐색부터 시작하자.

조건이 5 ≤ sequence의 길이 ≤ 1,000,000 이기 때문에

n^2로는 테스트 케이스에서 배열 길이가 조금만 길어져도 시간초과가 발생. 

 

 

2차 시도

public int[] solution(int[] sequence, int k) 
{
    int currentSum = 0;
    for(int length = 1; length <= sequence.Length; ++length)
    {
        currentSum = 0;

        for(int offset = 0; offset < length; ++offset) // 시작점에서 Length만큼 더한다.
            currentSum += sequence[offset];

        for(int i = 0; i <= sequence.Length - length; ++i) // 시작 인덱스
        {
            if(currentSum == k)
                return new int[2] { i, i + length - 1 };
            else if(currentSum > k)
                break;

            if(i == sequence.Length - length)
                break;

            currentSum -= sequence[i];
            currentSum += sequence[i + length];
        }
    }

    return null;
}

길이가 1개, 2개, 3개.... 증가시켜가며

부분합을 유지하고 맨 앞 숫자를 빼고 다음 숫자를 더하는 방식으로 최적화 해봤다.

그러나 수행시간이 거의 동일.

 

 

나의 풀이

public int[] solution(int[] sequence, int k) 
{
    int[] answer = new int[2];
    int minLength = int.MaxValue;

    int start = 0;
    int end = 0;
    int curSum = sequence[0];

    while(start < sequence.Length)
    {
        if(curSum < k)
        {
            ++end;

            if(end == sequence.Length)
                break;

            curSum += sequence[end];
        }
        else if(curSum == k)
        {
            // 하나의 쌍을 만들었다.
            int curLength = end - start + 1;
            if(curLength < minLength)
            {
                minLength = curLength;
                answer[0] = start;
                answer[1] = end;
            }

            curSum -= sequence[start];
            ++start;
        }
        else // curSum > k
        {
            curSum -= sequence[start];
            ++start;
        }
    }

    return answer;
}

투 포인터를 사용하니 통과하였다.

투 포인터는 start 가 0에서 N까지 증가 가능 O(N) + end가 0에서 N까지 증가 가능 O(N) 이기 때문에 O(N)의 수행시간이다.

 

기본 아이디어

1. 시작 포인터(start)와 끝 포인터(end)를 인덱스 0번을 가르키게 한다. (이 때 부분합은 sequence[0])

2. 부분합이 K보다 작다면 끝 포인터를 뒤로 옮기고 더해준다. (포인터가 범위값을 넘었다면 break)

3. 부분합이 K와 같다면 하나의 쌍을 만든 것이다. minLength랑 비교하고 그것 보다 작다면 교체한다.

 - 만약 문제가 부분합을 만족하는 순서쌍 갯수를 구하는 문제였다면 여기에서 카운트를 ++ 했을 것이다. 

4. 부분합이 K와 같거나 크다면 시작 포인터를 위치의 수를 뺀 다음 한 칸 뒤로 옮긴다.