109. 연속된 부분 수열의 합

 

 

기본 틀 :

 

using System;

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

 

처음 문제를 보고 Dictionary의 Key를 int형 배열로 잡고 Value를 int로 해서 

 

Key에는 시작과 끝 index를 저장, Value에는 개수를 저장해서

 

Value가 가장 작은 Key를 결과로 반환하고자 했다.

using System;
using System.Linq;
using System.Collections.Generic;

public class Solution {
    public int[] solution(int[] sequence, int k) {
        Dictionary<int[], int> dict = new Dictionary<int[], int>();
        for(int i = 0; i < sequence.Length; i++)
        {
            int startIndex = i, endIndex = i, sum = 0;
            
            for(; endIndex < sequence.Length; endIndex++)
            {
                sum += sequence[endIndex];
                if(sum >= k) break;
            }
            if(sum > k || sum < k) continue;
            
            dict.Add(new int[] { startIndex, endIndex }, endIndex - startIndex + 1);
        }
        
        int min = int.MaxValue;
        int[] result = null;
        
        foreach(var entity in dict)
        {
            if(entity.Value < min)
            {
                min = entity.Value;
                result = entity.Key;
            }
        }
        
        return result;
    }
}

 

그 결과,

 

"시간 초과"가 발생하게 됐다...

 

"시간 초과"가 발생하지 않게 바꾸기 위해 다른 알고리즘을 생각한 결과

 

 

	for(int i = 0; i < sequence.Length; i++)
        {
            int startIndex = i, endIndex = i, sum = 0;
            
            for(; endIndex < sequence.Length; endIndex++)
            {
                sum += sequence[endIndex];
                if(sum >= k) break;
            }
        }

 

위와 같이 startIndex와 endIndex를 이용해 sum을 구하는 과정을 잘 활용하면 된다는 사실을 파악해냈다.

 

그래서,

 

        int startIndex = 0, endIndex = 0, sum = sequence[0];

 

위와 같이 변수를 선언하고

 

        while(endIndex < sequence.Length)
        {

        }

 

while문으로 endIndex가 sequence.Length 보다 작을 경우 반복문이 계속 실행되게 설정하고

 

        while(endIndex < sequence.Length)
        {
            if(sum == k)
            {
                
            }
            else if(sum < k)
            {
                
            }
            else
            {
                
            }
        }

 

sum의 값에 따라 startIndex와 endIndex를 조정할 수 있도록 if문을 작성했다.

 

 

먼저,

 

sum이 k와 같은 경우는

            if(sum == k)
            {
                break;
            }

break 반복문을 종료하면 된다 판단했고,

 

sum < k 이면,

            else if(sum < k)
            {
                endIndex++;
                if(endIndex < sequence.Length)
                    sum += sequence[endIndex];
            }

endIndex가 sequence의 길이를 벗어나지 않는 선에서 증가시켜 sum의 값이 커지도록 만들어줬다.

 

반대로 sum > k이면,

            else
            {
                sum -= sequence[left++];
            }

 

sequece[left]로 왼쪽 범위를 줄여 sum의 값을 줄여줬다.

(sequence[left++]에서 left++은 후위 연산이라 sequence[left]가 먼저 동작 후 left++가 동작한다.)

 

전체 코드 : 

 

using System;
using System.Linq;

public class Solution {
    public int[] solution(int[] sequence, int k) 
    {
        int startIndex = 0, endIndex = 0, sum = sequence[0];
        int minLength = int.MaxValue;
        
        while(endIndex < sequence.Length)
        {
            if(sum == k)
            {
                break;
            }
            else if(sum < k)
            {
                endIndex++;
                if(endIndex < sequence.Length)
                    sum += sequence[endIndex];
            }
            else
            {
                sum -= sequence[startIndex++];
            }
        }
        
        return new int[] {startIndex, endIndex};
    }
}

 

그 결과,

 

테스트 2에서 값이 5가 되긴 하지만 최소 범위를 찾지 못 했다...

 

최소 범위를 찾기 위해 고민 끝에

 

        int startIndex = 0, endIndex = 0, sum = sequence[0];
        int minLength = int.MaxValue;
        int[] answer = new int[2];

 

minLength라는 변수와 answer 변수를 추가해주고

            if(sum == k)
            {
                if((endIndex - startIndex) < minLength)
                {
                    minLength = endIndex - startIndex;
                    answer[0] = startIndex;
                    answer[1] = endIndex;
                }
                sum -= sequence[startIndex++];
            }

 

현재 범위가 minLength 보다 작으면 minLength와 Index를 변경 및 sequence의 왼쪽 범위를

 

줄여 sum을 줄임과 동시에 범위가 더 작은 경우가 존재하는지 확인할 수 있도록 해주었다.

 

전체 코드 :

 

using System;
using System.Linq;

public class Solution {
    public int[] solution(int[] sequence, int k) 
    {
        int startIndex = 0, endIndex = 0, sum = sequence[0];
        int minLength = int.MaxValue;
        int[] answer = new int[2];
        
        while(endIndex < sequence.Length)
        {
            // 더한 값이 같은 경우
            if(sum == k)
            {
                // 연산에 사용된 최소 개수 비교
                if((endIndex - startIndex) < minLength)
                {
                    // 현재 최소 개수 저장 및 index 기록
                    minLength = endIndex - startIndex;
                    answer[0] = startIndex;
                    answer[1] = endIndex;   
                }
                
                // 다른 sum == k 인 경우가 존재할 수 있기 때문에 왼쪽 범위 줄이기
                sum -= sequence[startIndex++];
            }
            // sum이 k 보다 작을 경우
            else if(sum < k)
            {
                // 범위 늘리기
                endIndex++;
                
                // 범위를 벗어나지 않게 하기 위한 조건문
                if (endIndex < sequence.Length)
                    sum += sequence[endIndex];
            }
            // sum이 클 경우 왼쪽에서 부터 범위 줄이기
            else
            {
                sum -= sequence[startIndex++];
            }
        }
        
        return answer;
    }
}