[백준] 2003_수들의 합 2 C++

12 Jan 2024 in Study on Coding Test

시간복잡도를 신경써야 했던 투 포인터 문제

정답제출코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N, M;
vector<int> vec;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;

    for (int i = 0; i < N; ++i)
    {
        int _input;
        cin >> _input;

        vec.push_back(_input);
    }

    
    int ans = 0;

    int left = 0, right = 0;

    int Mid = vec[left];

    while (left <= right && right < N)
    {   
        if (Mid == M)
        {
            ans++;
            Mid += vec[++right];
        }

        else if (Mid > M)
        {
            Mid -= vec[left++];

            if (left > right)
            {
                right = left;
                Mid = vec[left];
            }
        }

        else
            Mid += vec[++right];
    }

    cout << ans;

    return 0;
}

오답제출코드(시간초과)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N, M;
vector<int> vec;

int Sum(int a, int b)
{
    int ret = 0;
    for (int i = a; i <= b; ++i)
        ret += vec[i];
    return ret;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;

    for (int i = 0; i < N; ++i)
    {
        int _input;
        cin >> _input;

        vec.push_back(_input);
    }

    
    int ans = 0;

    for (int i = 0; i < N-1; ++i)
    {
        int left = i, right = N-1;

        while (left <= right)
        {
            int Mid = Sum(left, right);
            
            if (Mid == M)
            {
                ans++;
                right--;
            }

            else if (Mid > M)
                right--;
            
            else
                break;
        }
    }

    cout << ans;

    return 0;
}

시간초과가 났다.

실버 문제라고 방심했다가 0.5초라는 시간제한을 보지 않았다.

여기서 파악한 문제점은 포인터를 옮길 때 마다

Sum 함수를 계속 돌려주어 시간복잡도가 O(N^2)으로 늘어났다는 점이다.

그래서 코드를 정답코드와 같이 변환해주었다.

투 포인터를 양쪽에서 좁혀오는 방식만 기억하고 있었다.

하지만 그런 방식만 있는게 아니라 두 개의 포인터 모두 처음에서 시작하여

하나씩 옮겨가는 방식도 이번에 다시 기억하게 되었다.

코딩테스트 실력이 많이 녹슬었다. 실버, 기초 문제부터 다시 풀면서

기억을 되살려야겠다.