코딩테스트 -- 연속된 부분 수열의 합 - (프로그래머스 / C++)

프로그래머스

문제!

---

비내림차순으로 정렬된 수열이 주어질 때, 다음 조건을 만족하는 부분 수열을 찾으려고 합니다.

 

1.기존 수열에서 임의의 두 인덱스의 사이 원소를 모두 포함해야한다

2. 부분수열의 합은 k

3. 부분수열이 가장짧은 수열/ 가장 앞에 나오는 수열을 찾아야한다.

---

위의 3가지 조건을 만족하는 부분수열을 찾는 문제였습니다. 

 

저는 먼저 부분합 배열을 만들어 주고 합이 k가 되는 모든 수열 인덱스를 저장해두고 

정렬을 시켰으나... 시간초과 나네요..

 

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

int save[1000001]={0,};

vector<pair<int,int>>answerList;


bool tmp(pair<int,int> a , pair<int,int>b){
    if(a.second-a.first>b.second-b.first){
        return false; // 차가 작은순으로 내림차순 >> 원래 오름차순이였다 생각하고 false면 내림차순
    }
    else if(a.second-a.first==b.second-b.first){
        if(a.first>b.first){
            return false;
        } 
    }
    
    return true;
}


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

    
    save[0]=0;
    save[1]=sequence[0];
    
    for(int i=2;i<sequence.size()+1;i++){
        save[i]=save[i-1]+sequence[i-1];
    }
        
    
    
    for(int i=0;i<sequence.size();i++){ // 시작점
        for(int j=i+1;j<sequence.size()+1;j++){ // 끝점
            if(save[j]-save[i]==k){
                answerList.push_back({i,j-1});
            }
        }
    }
    
    
    sort(answerList.begin(),answerList.end(),tmp);
        
    
    answer.push_back(answerList[0].first);
    answer.push_back(answerList[0].second);
    
    return answer;
}

 

여기서 조금더 생각해보니 정렬부분은 굳이 필요가 없는거 같더라구요??

 

그래서 그 부분만 수정한 코드도 시간초과....

부분 수열로 만들어서 풀면 길이가 100000개인 배열을 2개씩 잡고 비교해서 시간초과가 나는것 같네요

for(int i=0;i<sequence.size();i++){ // 시작점
        for(int j=i+1;j<sequence.size()+1;j++){ // 끝점
            if(save[j]-save[i]>k || sumTemp<=j-1-i){
                i+=1;
                j=i+1;
            }
            else if(save[j]-save[i]==k){
                if(sumTemp>j-1-i){ // 작다
                    StartPoint=i;
                    EndPoint=j-1;
                    sumTemp=j-1-i;
                    
                    i+=1;
                    j=0;
                }
                else if(sumTemp==j-1-i){//같다
                    if(StartPoint>i){
                        StartPoint=i;
                        EndPoint=j-1;
                    }
                }
            }
        }
    }

 

그래서 좀 더 찾아보고 난 마지막 방법 투포인터!

 

시작점과 끝점을 0 으로 잡고 k가 되는 부분수열 부분으로 이동시키며 확인하는 방법입니다. 

 

여기서 가장 중요한 부분은 

 

 

ex) 1 2 3 4 5   , k=10 에서 만약 1 2 3 4 부분에서 k=10 답을 맞췄다고 할때

이 부분수열의 안쪽은 탐색하지 않아도 된다!

1 2 , 1 2 3,  2 3 4,  3 4 등등

 

 

그렇기에 Endtpoint를 상승시켜 k가 되는 지점, 넘는 지점을 찾고

startpoint도 상승시켜 k가 되는 지점을 찾아주고 이런 방식을 계속 반복하여

Endtpoint-startpoint + 1 =k 가 되는지점, startpoint 가 최소가 되는 지점을 찾을 수 있습니다!

while(StartPoint<=EndPoint&&EndPoint<sequence.size()){
        if(sum<k){
            EndPoint++;
            sum+=sequence[EndPoint];
            continue;
        }
        else if(sum==k){
            if(EndPoint-StartPoint+1<sumTemp){
                sumTemp=EndPoint-StartPoint+1;
                answer[0]=StartPoint;
                answer[1]=EndPoint;
            }
            else if(EndPoint-StartPoint+1==sumTemp){
                if(answer[0]>StartPoint){
                    answer[0]=StartPoint;
                    answer[1]=EndPoint;
                }
            }
            
        }
        sum-=sequence[StartPoint];
        StartPoint++;
    }

 

 

끝!

 

 

 

 

 

ALL

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

vector<int> solution(vector<int> sequence, int k) {
    vector<int> answer={0,0};
    int sumTemp=sequence.size()+1; // 부분수열의 길이 
    int sum=sequence[0];
    int StartPoint=0;
    int EndPoint=0;
    


    while(StartPoint<=EndPoint&&EndPoint<sequence.size()){
        cout<<StartPoint<<" "<<EndPoint<<endl;
        if(sum<k){
            EndPoint++;
            sum+=sequence[EndPoint];
            continue;
        }
        else if(sum==k){
            if(EndPoint-StartPoint+1<sumTemp){
                sumTemp=EndPoint-StartPoint+1;
                answer[0]=StartPoint;
                answer[1]=EndPoint;
            }
            else if(EndPoint-StartPoint+1==sumTemp){
                if(answer[0]>StartPoint){
                    answer[0]=StartPoint;
                    answer[1]=EndPoint;
                }
            }
            
        }
        sum-=sequence[StartPoint];
        StartPoint++;
    }
    
    

    
    return answer;
}

 

 

 

 

틀린점이 있다면 댓 달아주세요!