연속된 부분 수열의 합(32분: 44점)

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

구현 아이디어 5분 구현 27분

시간 초과 이슈가 있는 풀이다. 총 점 44점. DFS 말고 슬라이딩 윈도우를 써서 다시 풀어보자.

틀린 이유

비내림차순이라는 말에 정렬 없이 아예 마구 섞인 배열이라 생각했다. 그래서 DFS를 통해 조합을 전부 구했더니 시간 초과가 떴다. 비내림차순은 중복 값이 있을 수 있는 오름차순이라고 한다.

틀린 풀이

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

using namespace std;
int ch[2];
int len = 2147000000;
vector<int> answer;

void DFS(int L, int e, int i, const vector<int>& sequence, int k)
{
    if(L == e)
    {
        int l = ch[1] - ch[0];
        if(len < l) return;
        
        int sum = 0;
        for(int i = ch[0]; i <= ch[1]; ++i)
        {
            sum += sequence[i];
        }
        
        if(sum != k) return;
        if(len == l)
        {
            if(answer[0] < ch[0]) return;
        }
        
        answer.clear();
        
        answer.push_back(ch[0]);
        answer.push_back(ch[1]);
        
        len = l;
    }
    else
    {
        for(; i < sequence.size(); ++i)
        {
            ch[L] = i;
            DFS(L + 1, e, i, sequence, k);
        }
    }
}

vector<int> solution(vector<int> sequence, int k) {
    int N = sequence.size();
    DFS(0, 2, 0, sequence, k);
    return answer;
}

---

틀린 풀이

슬라이딩 윈도우를 사용한 풀이인데 시간 초과가 떴다. 58점. 코드도 지저분해서 마음에 안 든다. sequence 배열의 길이가 1,000,000기 때문에 최악의 경우 길이가 1인 슬라이딩 윈도우에서 1,000,000인 슬라이딩 윈도우를 계산하게 된다.

부분 수열이 가변 길이기 때문에 투포인터를 앞뒤에서 움직여가며 한번의 순회에서 찾자.

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> sequence, int k) {
    vector<int> answer;
    
    int N = sequence.size();
    int lp = 0, rp = 0;
    int sum = 0;
    
    for(int i = 0; i < N; ++i)
    {
        if(sequence[i] == k)
        {
            answer.push_back(i);
            answer.push_back(i);
            return answer;
        }
    }
    
    for(int i = 1; i < N; ++i)
    {
        lp = 0;
        rp = i;
        
        sum = 0;
        for(int j = 0; j <= rp; ++j)
            sum += sequence[j];
        
        if(sum == k)
        {
            answer.push_back(lp);
            answer.push_back(rp);
            return answer;
        }
        
        for(++rp; rp < N; ++rp, ++lp)
        {
            sum += sequence[rp];
            sum -= sequence[lp];
            
            if(sum == k)
            {
                answer.push_back(lp + 1);
                answer.push_back(rp);
                return answer;
            }
        }
    }
    
    return answer;
}

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> sequence, int k) {
    vector<int> answer;
    
    int N = sequence.size();
    
    // 부분 수열의 길이.
    int len = 1;
    
    for(; len <= N; ++len)
    {
        int rp = 0;
        int sum = 0;
        
        for(int lp = 0; lp < N; ++lp)
        {
            // 초기 sum 값 만듦.
            if(lp == 0)
            {
                for(; rp < len; ++rp)
                    sum += sequence[rp];
                
                --rp;
            }
            
            // lp가 1일 때부터 else문.
            else
            {
                sum -= sequence[lp - 1];
                if(rp == sequence.size()) 
                {
                    rp = 0;
                    break;
                }
                sum += sequence[++rp];
            }
            
            if(sum == k)
            {
                answer.push_back(lp);
                answer.push_back(rp);
                
                return answer;
            }
        }
    }
    
    return answer;
}

---

풀이

https://ksb-dev.tistory.com/302

위의 글을 읽고 공부했다. 그림이 있어 이해하기 편하다! 투포인터 활용.

1. 처음 sum과 lp, rp를 세팅하고 while문에 들어간다.
2. sum 값이 k보다 크다면 lp를 움직인다.
3. sum 값이 k보다 작다면 rp를 움직인다.
4. sum 값이 k와 같다면 rp를 움직인다.

• 모든 경우에서 rp가 배열의 끝에 도달해 있다면 lp를 움직인다.

#include <iostream>
#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> sequence, int k) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    vector<int> answer;
    vector<pair<int, int>> res;
    
    int lp = 0, rp = 0;
    int N = sequence.size();
    int sum = 0;
    
    sum += sequence[lp];
    sum += sequence[rp];
    sum /= 2;
    
    while(true)
    {
        if(lp == N - 1 && rp == N - 1)
        {
            if(sum == k)
                res.push_back(make_pair(lp, rp));
            
            break;
        }
        
        if(sum == k)
        {
            res.push_back(make_pair(lp, rp));
            
            if(rp != N - 1) sum += sequence[++rp];
            else sum -= sequence[lp++];
        }
        else if(sum > k)
        {
            if(lp != N - 1)
            {
                if(lp == rp) break;
                
                sum -= sequence[lp++];
            }
        }
        else if(sum < k)
        {
            if(rp != N - 1) sum += sequence[++rp];
            else sum -= sequence[lp++];
        }
    }
    
    //for(auto it : res)
    //   cout << it.first << ", " << it.second << endl;
    
    int mini_index = 2147000000;
    int mini_len = 2147000000;
    
    for(auto it : res)
    {
        // 길이가 짧은 것이 우선이다.
        int len = it.second - it.first;
        if(len >= mini_len) continue;
        
        mini_len = len;
        
        // 길이가 더 짧다면.
        answer.clear();
        answer.push_back(it.first);
        answer.push_back(it.second);
    }
    
    return answer;
}