2003. 수들의 합 2

2003. 수들의 합 2

 

 

전형적인 전진 투 포인터 문제다.

• l, r이 모두 0부터 시작하는 투 포인터다.
• 현재 값이 목표 값보다 크면 l을 하나씩 당겨주고, 작으면 r을 하나씩 늘려주는 방식이다.
• 조건을 만족하는 가장 빠른 구간을 찾거나, 조건을 만족하는 구간의 개수를 찾을 때 유용하다.

 

l, r이 모두 n에 도달할 때까지 반복하고, 항상 l ≤ r이므로 r이 n에 도달한 이후에는 l만 증가시켜주는 로직이 들어가야 한다.

 

#include <iostream>
#include <vector>

using namespace std;

int TwoPointers(vector<int>& v, int M)
{
    int answer = 0;
    size_t n = v.size();
    int l = 0, r = 0, sum = v[0];

    while (l < n || r < n)
    {
        if (sum <= M)
        {
            answer += (sum == M);
            
            if (++r < n)
                sum += v[r];
            else
                sum -= v[l++];
        }
        else
        {
            sum -= v[l++];
        }
    }

    return answer;
}

int main(int argc, char* argv[])
{
    int N, M;
    cin >> N >> M;

    vector<int> v(N);
    for (int i = 0; i < N; ++i) cin >> v[i];

    cout << TwoPointers(v, M);

    return 0;
}

 

좀 더 간단한 방식이다.

 

전진 투 포인터에서는 범위를 [l, r)로 구성하는 것이 인덱스 계산이 쉽다.

• 단, r의 범위 검사는 꼭 순서대로 중간에 위치해야 한다.

 

#include <iostream>
#include <vector>

using namespace std;

int TwoPointers(vector<int>& v, int M)
{
    int answer = 0;
    size_t n = v.size();
    int l = 0, r = 0, sum = 0;

    while (l <= r)
    {
        if (M <= sum)
            sum -= v[l++];
        else if (n <= r)
            break;
        else
            sum += v[r++];

        answer += (sum == M);
    }

    return answer;
}

int main(int argc, char* argv[])
{
    int N, M;
    cin >> N >> M;

    vector<int> v(N);
    for (int i = 0; i < N; ++i) cin >> v[i];

    cout << TwoPointers(v, M);

    return 0;
}