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

 

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

 

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

프로그래머스

---

 

 

해결전략

 

누적합

슬라이딩 윈도우(Sliding Window) 알고리즘

---

 

 

처음 시도한 코드 - 실패

 

#include <vector>
using namespace std;

vector<vector<int>> v; // 시작Idx x 끝Idx. 값은 부분 수열의 합

vector<int> solution(vector<int> seq, int k) {
    vector<int> answer(2, -1); // 조건을 만족하는 부분 수열의 시작Idx와 끝Idx 담기
    int dif = 2147000000;

	int n = seq.size();
    v.resize(n, vector<int>(n));

    v[0][0] = seq[0];
    int i = 0;
    for(int j=1; j<n; j++)
    {
        v[i][j] = v[i][j - 1] + seq[j];

    	if (v[i][j] > k) // 부분합이 k초과
        {
            int x = 0;
			while(v[i][j] > k)
			{
                v[i][j] -= seq[x];
                x++;
			}
            v[x][j] = v[i][j];
            i = x;
        }

        if (v[i][j] == k) // 합이 k인 경우
        {
            if (j - i < dif)
            {
                dif = j - i;
                answer[0] = i;
                answer[1] = j;
            }
        }

        if (seq[j] == k) // 한 숫자가 k인 경우
        {
            answer[0] = j;
            answer[1] = j;
            break;
        }
    }

    return answer;
}

 

 

---

 

정답코드

 

#include <vector>
using namespace std;

vector<int> solution(vector<int> seq, int k) {
    vector<int> answer(2, -1); // 조건을 만족하는 부분 수열의 시작Idx와 끝Idx 담기

	int dif = 2147000000; // 끝Idx(=end) - 시작Idx(=start) 초기값을 int 최대값으로 지정
    int n = seq.size();
    seq.resize(n + 1); // 마지막 변수가 범위를 +1 벗어난다. sum += seq[end++];에서 seq[(n-1)++]하면 추가로 +1 더 필요하다.

    int start = 0, end = 0, sum = 0;
    while(end < n+1)
    {
        if (sum == k)
        {
            if (end - start < dif) {
                dif = end - start;
                answer[0] = start;
                answer[1] = end-1; // sum < k일 때, seq[end++];에서 end++이 된다. 따라서 현재 시점보다 +1인 end 변수값이기 때문에 -1 해준다. 

                if (dif == 0) break;
            }

            sum -= seq[start++];
        }
        else if (sum > k)
        {
            sum -= seq[start++];
        }
        else if (sum < k)
        {
            sum += seq[end++];
        }
    }

    return answer;
}

 

---