560. Subarray Sum Equals K

https://leetcode.com/problems/subarray-sum-equals-k/description/

Subarray Sum Equals K - LeetCode

 

Q. 주어진 배열 nums에서 연속된 subArray의 합이 k 와 같은 해당 subArray 수를 구하라.

 

Solution. 

  생각해 볼 것이 좀 있는 문제다. 

  우선 2중 for 문을 돌면서 찾는 방법을 생각해 보자. 

   ex) [1, 2, 3] -- k : 3 

   1부터 시작해서 2, 와 3을 까지 도달하며 3이 되는 sub arry가 있나 조회하면 1,2 하나 있다. 

   다음, 2로 시작해서 3까지 가면서 더해 보면 없다. 

   마지막 3에서 시작하면 바로 그 값이 k 므로 하나 있다. 

   최종 더한 모든 경우의 수는 2가지 이다.   

   수행시간은 O(NxN)으로 답은 찾겠지만, 최적해는 아닌것 같다. 

 

  구간의 합을 생각하는 방식으로 방향을 조금 전환해 보자. 

   0에서 특정 수 m까지의 의 구간합을 S(m)라고 하자. 

   0에서 다른 특정 수 n까지의 구간합을 S(n)이라고 하자. 

   m>n 일때, S(m)-S(n) == k 가 되면 해당 sub array가 있다고 할수 있는지 생각해 보자. 

   . 

   . 

   . 

   가능하다. 

   [1, 2, 3] 을 각 구간 합으로 재표기 하면 

   [1, 3, 6] 이 된다. 

   이 때, 더 앞서있는 구간합에서 뒤쳐진 어느 구간합을 뺐을때, k, 즉 3이 된다면 해당 구간이 있다는 것이다. 

   여기서는 앞서와 같이 두가지 경우

    m이 1일때 구간합은 3, 그리고 n은 시작 전(구간합-0)일 때 한번 성립, (3-0 == 3(k)) 

    m은 2일때 구간합 6, 그리고 n은 1일때 구간합 3, 즉 6-3=3(k) 이므로 또 한번 성립한다.  

   

   조금 더 복잡한 경우도 확인해 보자. 

   [10, 5, 2, 1, -3, 10, 5] , k (8)

    눈으로 확인해 보면, 5, 2, 1 (=> idx[1, 2, 3]) 그리고 1, -3, 10 (=> idx[3,4,5]) 의 두개의 해가 존재함을 알수 있다. 

    하지만 위의 로직으로 다시 한번 살펴보자. 

   [10, 15, 17, 18, 15, 25, 30] 이 구간합이 된다. 

   이때 먼저 간 구간합에서 덜 간 구간합을 빼서 k(8)이 되는 녀석이 있나 살펴보자. 

    18 - 10 = 8 (S[3] - S[0])  => Sum of indices of [1, 2, 3]

    25 - 17 = 8 (S[5] - S[2])  => Sum of indices of [3, 4, 5]

    

    정리해 보자. 

 

    즉, 합의 누적 계산을 시작하는 구간이 다르더라도, 접근 방법을 구간합 방식으로 변경하면, 

    특정 구하고자 하는 구간합(k)는, 구간합(m)에 더 적은 구간합(n)을 제회했을 때 적어도 하나 이상 존재해야 한다. 

    즉, 이 수가 구하고자 하는 구간합 k의 sub array 수가 된다.  

 

    코드로 다시 정리해 보자. 

 int subarraySum(vector<int>& nums, int k) 
 {
	vector<int> areaSum;
    int sum = 0;
    // 모든 구간합을 미리 구해 놓는다.
    for (int q = 0; q < nums.size(); ++q)
    {
        sum += nums[q];
        areaSum.push_back( sum );
    }

    int target = k;
    int ret = 0;
    // 두 수(구간합)의 차가 target이 되는지 확인한다.
    for (int q = 0; q < areaSum.size(); ++q)
    {
        if (areaSum[q] == target)   // 이 자체 구간합이 같으면 처음부터 더한 구간합이라는 의미.
            ++ret;
        for (int j = 0; j < q; ++j)
        {
            if (areaSum[q] - areaSum[j] == target)
                ++ret;              // 이전 모든 구간합을 때 보면서 target값이 있나 찾아 본다.
        }
    }
    return ret;
 }

 

 

열심히 로직 재정리를 했는데, TC 를 초과 해 버렸다. 

 

로직은 재정리 됐지만, TC는 O(NxN)으로, 이에 대한 최적화는 아직 되지 않은 때문이다. 

 

다시 TC를 더 최적화를 할수 있는 방안을 고민해 보자. 

 

다시 마지막 문단 중첩 for문을 사용하는 구조를 보니, 두 수의 차가 특정 수일 경우를 찾는 경우이다. 

이런 경우 문제를 어디서 종종 본것 같다. 

바로 map을 사용해서 합이나 차의 결과값을 바로 조회 할수 있는 방법을 익숙히 알고 있을 것이다. 

해당 알고리즘을 적용해 본다. 

 

int subarraySum(vector<int>& nums, int k) 
{
	int sum = 0;
    int target = k;
    int ret = 0;
    map<int, int> mapFreq;
    mapFreq[0] = 1;         // 처음부터의 구간합일 경우 고려.(뒤 차감 구간합이 필요없는 경우) 
    for (int q = 0; q < nums.size(); ++q)
    {
        sum += nums[q];
        
        // 알고리즘에 의해 이전에 이런 구간합이 몇개 있었나 조회하고 합산.
        if (mapFreq.find(sum - target) != mapFreq.end())
            ret += mapFreq[sum - target];

		// 모든 구간 합 및 빈도들을 map에 저장.
        // 다만, 반드시 조회 후에 현재 구간합을 더할 필요가 있음.
        mapFreq[sum]++;     
    }
    return ret;
 }

 

 hash를 사용해서 위와 같이 코드를 정리 할 수 있다. 

 다만, 현재 보다 뒤쳐진 구간합에 대해서만 조회가 필요하므로, map 구성과 동시에 검색이 가능하다. 

  

 

  다시 문제를 정리 해 보면, 

  우선, 구간 합 방식으로 논리를 재정리 해야 하고, 

  이후는 두수를 찾는 문제이므로, 해시를 사용하여 대상 검색을 최적화 한다.  

 

- 좋은 문제. -

 

Note) 24.04.05 - 이 문제는 다시 만났는데, 여전히 풀기 실패. 다시 머리속에 새겨 본다. 

 연속된 sub array의 합이 target이 되는 경우, .. 현재 구간합에 이전 구간합의 차감이 target이 되는 경우가 몇개가 있나 셈.. 음....