[Programmers] Lv2. 연속된 부분 수열의 합 | C++

🔗문제 보러가기

프로그래머스

 

👨‍💻풀이 과정

 

입력 데이터 크기가 1,000,000개이니 당연히 \( O(n^2) \)으로는 못 풉니다. 즉, 이중 반복문으로는 어렵겠다고 생각하였습니다. 그래서 저는 두 개의 인덱스 변수를 통해, 반복문을 한 번만 돌도록 풀이를 구상하였습니다.

 

• 시작 인덱스(startIdx), 끝 인덱스(lastIdx), 합계 변수(sum)를 모두 0으로 초기화하여 선언합니다.
• startIdx <= lastIdx 이고, lastIdx < sequence.size()라면, while문을 돌아줍니다.
  • sum + sequence[lastIdx] == k라면, 답의 후보 중 하나이므로 별도로 저장해 놓습니다.
  • sum + sequence[lastIdx] < k라면, sum += sequnece[lastIdx++]
  • sum + sequence[lastIdx] >= k라면, sum -= sequnece[startIdx++]
  • 위와 같이 조건문들을 지정하여 반복해줍니다.
• 반복문이 끝났다면, 짧은 길이의 수열이 앞 쪽으로 가도록 정렬해줍니다.
  • 길이가 같다면, 시작 인덱스가 작은 게 앞으로 가도록 해줍니다.
• 정렬 후, 첫 번째 후보의 시작 인덱스와 끝 인덱스를 배열에 담아 리턴해줍니다.

 

✏️소스 코드 및 결과

#include <vector>
#include <algorithm>
using namespace std;

bool Compare(const pair<int, int>& n1, const pair<int, int>& n2) {
    int n1Difference = abs(n1.first - n1.second);
    int n2Difference = abs(n2.first - n2.second);

    if (n1Difference == n2Difference)
        return n1.first < n2.first;
    return n1Difference < n2Difference;
}

vector<int> solution(vector<int> sequence, int k) {
    vector<pair<int, int>> candidates;
    int startIdx = 0, lastIdx = 0;
    int sum = 0;

    while (startIdx <= lastIdx and lastIdx < sequence.size()) {
        int nextSum = sum + sequence[lastIdx];
        
        if (nextSum == k)
            candidates.emplace_back(startIdx, lastIdx);

        if (nextSum < k)
            sum += sequence[lastIdx++];
        else
            sum -= sequence[startIdx++];
    }

    sort(candidates.begin(), candidates.end(), Compare);
    vector<int> answer {candidates[0].first, candidates[0].second};
    return answer;
}