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

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

프로그래머스

[문제 요약]

 오름차순으로 정렬된 배열에서 연속된 수들의 합이 k 와 같은 집합에서 원소의 개수가 가장 적으면서 시작 index가 가장 낮은 수열의 시작과 끝 index를 구하는 문제.

 

[풀이]

• 투포인터 문제 O(N)에 풀린다.
• 세가지의 조건이 필요하다
  • k > sum[s,e] : e(end) pointer를 증가시켜 sum의 값을 증가시킨다.
  • k < sum[s,e] : s(start) pointer를 증가시켜 sum의 값을 감소시킨다.
  • k == sum[s,e] : 현재까지의  candidates 중 길이가 가장 짧은 부분 수열의 s, e로 교체 (길이가 같을 때 index는 순서대로 증가하기 때문에 같은 경우를 고려하지 않으면 s의 index는 최소가 된다.)

 

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> sequence, int k) {
	vector<int> answer;

	auto sz = sequence.size();
	int sum = 0, minVal = sz;
	pair<int, int> candidate = {0, sequence.size() - 1};

	for (int s = 0, e = 0; s < sz;) {
		if (sum == k && minVal > (e - s)) {
			candidate.first = s;
			candidate.second = e - 1;
			minVal = (e - s);
		}
		else if (sum < k && e < sz) {
			sum += sequence[e++];
		}
		else {
			sum -= sequence[s++];
		}
	}

	answer.push_back(candidate.first);
	answer.push_back(candidate.second);

	return answer;
}

 

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> sequence, int k) {
	vector<int> answer(2, 0);

	int st = 0, sm = 0, len = 1e9;

	for (int i = 0; i < sequence.size(); i++) {
		sm += sequence[i];

		while (sm > k) {
			sm -= sequence[st++];
		}

		if (sm == k) {
			if (len > i - st) {
				len = i - st;
				answer[0] = st;
				answer[1] = i;
			}
		}
	}

	return answer;
}