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

 

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

 

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

---

 

 

해결전략

 

누적합

슬라이딩 윈도우(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;
}

 

---