[프로그래머스 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;
}
'⭐ 코딩테스트 > 프로그래머스' 카테고리의 다른 글
[프로그래머스 C++] 무인도 여행 (0) | 2023.11.17 |
---|---|
[프로그래머스 C++] 124 나라의 숫자 (0) | 2023.11.16 |
[프로그래머스 C++] 두 큐 합 같게 만들기 (0) | 2023.11.14 |
[프로그래머스 C++] 삼각 달팽이 (0) | 2023.11.13 |
[프로그래머스 C++] 다리를 지나는 트럭 (0) | 2023.11.10 |
댓글
이 글 공유하기
다른 글
-
[프로그래머스 C++] 무인도 여행
[프로그래머스 C++] 무인도 여행
2023.11.17 -
[프로그래머스 C++] 124 나라의 숫자
[프로그래머스 C++] 124 나라의 숫자
2023.11.16 -
[프로그래머스 C++] 두 큐 합 같게 만들기
[프로그래머스 C++] 두 큐 합 같게 만들기
2023.11.14 -
[프로그래머스 C++] 삼각 달팽이
[프로그래머스 C++] 삼각 달팽이
2023.11.13