프로그래머스 연속된부분수열의합 c++ // 정렬된 입력은 이분탐색, 누적합

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

프로그래머스

1. 의사코드

0. 오름차순 정렬조건 -> 이분탐색은 정렬시에만 사용가능하다 -> 이분탐색을 이용해 보자!

1. 누적합배열을 만들고

2. 예외처리 : 누적합에 정답(k)가 있는경우 누적합 정의에따라 [0,해당idx]가 정답후보임

3. 누적합배열을 돌면서, k + v[i]가 존재한다면, [i+1, 찾은idx]가 정답후보임

// +임에 주의, 3 일경우 10을찾아야 10-3 == 7(k) 가 됨

4. 시간복잡도 : 시퀀스 순회 100000 * 이분탐색(log2 100000) -> 가능

 

2. 전체코드

#include <bits/stdc++.h>

using namespace std;

int a[1000004];
vector<int> v;//누적합

vector<int> solution(vector<int> sequence, int k) {
    vector<int> answer;
    v.push_back(sequence[0]);
    for(int i=1;i<sequence.size();++i){
        v.push_back(sequence[i]+v[i-1]);
    }
    
    int mindist=987654321;
    
    //바로찾은경우
    int idx=lower_bound(v.begin(),v.end(),k)-v.begin();
        if(binary_search(v.begin(),v.end(),k)) {
            int dis=idx;
            if(mindist>dis){
                mindist=dis;
                answer={0,idx};
            }
            else if(mindist==dis){
                if(answer[0]>0)
                answer={0,idx};
            }
                //continue;
        }
    
    for(int i=0;i<sequence.size();++i){
        int idx=lower_bound(v.begin()+i+1,v.end(),k+v[i])-v.begin();
        
        if(binary_search(v.begin()+i+1,v.end(),k+v[i])==0) continue; //없으면 패스
        int dis=idx-i-1;
        if(mindist>dis){
            mindist=dis;
            answer={i+1,idx};
        }
        else if(mindist==dis){
            if(answer[0]>i+1)
            answer={i+1,idx};
        }
    }
    
    return answer;
}