Level 2. 연속된 부분 수열의 합

Level 2. 연속된 부분 수열의 합

 

 

가장 길이가 짧은 수열 중 가장 앞 쪽에 위치한 수열을 찾는 데에는 map<int, set<vector<int>>> 자료형을 사용했다.

 

l - r로 계산한 수열의 길이를 map에 넣어 map의 첫 번째에 가장 길이가 짤은 수열들이 위치하게 하고, map의 각 원소는 vector<int>를 원소로 갖는 set을 저장해 가장 앞 쪽에 위치한 원소가 첫 번째에 오도록 한다.

• vector는 비교 연산을 지원한다.

 

첫 번째 시도에서는 이중 for문을 통해 모든 경우의 수를 확인해서 시간 초과가 발생했다.

 

// 이 풀이는 시간 초과가 발생한다.
#include <iostream>
#include <vector>
#include <map>
#include <set>

using namespace std;

vector<int> solution(vector<int> sequence, int k)
{
    map<int, set<vector<int>>> mp;
    size_t size = sequence.size();

    for (int i = 0; i < size; ++i)
    {
        int sum = 0;

        for (int j = i; j < size; ++j)
        {
            sum += sequence[j];

            if (sum == k)
                mp[j - i].emplace(vector<int> {i, j});

            if (k <= sum)
                break;
        }
    }

    return *mp.begin()->second.begin();
}

 

두 번째 시도에서는 다른 방법을 시도했다가 실패했다.

 

배낭 문제를 떠올리며 수열의 길이를 짧게 하기 위해서는 큰 원소부터 넣어야 한다고 생각해 뒤에서부터 진행했고, 앞으로 같은 수가 연속된 만큼 당겨주면 된다고 생각했는데 오답이었다.

 

// 이 풀이는 틀린 풀이다.
#include <iostream>
#include <vector>

using namespace std;

vector<int> solution(vector<int> sequence, int k)
{
    int l = sequence.size() - 1;
    int r = l, sum = sequence[r];

    while (sum != k)
        if (sum < k)
            sum += sequence[--l];
        else
            sum -= sequence[r--];

    while ( (0 < l) && (sequence[l] + sequence[r] == sequence[l - 1] + sequence[r - 1]) )
        --l, --r;

    return {l, r};
}

 

결국, 다른 사람의 풀이를 참고해 풀 수 밖에 없었다.

 

단 번에 찾을 수 있는 방법이 있을 줄 알았는데 그런 건 없었다.

 

앞에서부터 더 이상 진행이 불가능할 때까지 그냥 모든 수열을 집어넣는 방식이었다..

 

#include <iostream>
#include <vector>
#include <map>
#include <set>

using namespace std;

vector<int> solution(vector<int> sequence, int k)
{
    int l = 0, r = -1;
    int sum = 0;
    size_t size = sequence.size();
    map<int, set<vector<int>>> mp;

    do
    {
        if (sum < k && ++r < size)
            sum += sequence[r];
        else
            sum -= sequence[l++];

        if (sum == k)
            mp[r - l].emplace(vector<int> {l, r});
    }
    while (r < size && l < size);

    return *mp.begin()->second.begin();
}

 

r을 증가시키며 끝을 고정해놓고 투 포인터를 진행한 방식이다.

 

수열들을 담아놓고 마지막에 확인하지 않고 매번 길이만 확인한다.

 

이렇게 r을 고정시켜 증가시키면서 확인하면 가장 앞 쪽에 있는 수열을 순서대로 확인함을 보장할 수 있다.

 

#include <iostream>
#include <vector>

using namespace std;

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

    int l = 0, r = 0, sum = 0;

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

        while (sum > k)
            sum -= sequence[l++];

        if (sum == k)
            if (answer.empty() || r - l < answer[1] - answer[0])
                answer = {l, r};
    }

    return answer;
}