[프로그래머스] Level 2. 연속된 부분 수열

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

프로그래머스

 

 

1. 실패코드 

그냥 처음부터 더해가면서 합이 k인 부분을 찾는 직관적인 방법 -> 시간초과 발생

#include <string>
#include <vector>

using namespace std;
int s = -1; int e = -1;
void change_answer(vector<int>& seq, int i, int j){
    if(s == -1){
        s = i; e = j;
        return;
    }
    
    if(j-i > e-s) return;
    if(j-i < e-s){
        s = i; e = j; return;
    }
    
    if(i<s){
        s = i; e = j; return;
    }
    
}
vector<int> solution(vector<int> sequence, int k) {
    vector<int> answer;
    
    for(int i=0;i<sequence.size(); i++){
        int sum = 0;
        for(int j=i; j<sequence.size(); j++){
            sum += sequence[j];
            if(s != -1 && e-s < j-i)break;
            if(sum <k) continue;
            else if(sum >k) break;
            
            change_answer(sequence, i,j);
            break;
        }
    }
    answer.push_back(s);
    answer.push_back(e);
    return answer;
}

 

 

2. 성공코드

그래서 s = 0, e = 0에서부터 시작해서 뒤에서넣고, 앞에서 빼면서 계산하는 방식으로 변경하였다. 

1. 만약 sum이 k보다 크다면, s에서부터 시작하는 수열검사는 끝났으므로, sum에서 s번째값을 뺀 뒤 s+1을 한다. (sum이 k보다 크지 않을때까지 계속 빼준다.)
2. 만약 sum 이 k보다 작다면, 뒤에있는 요소를 추가한 뒤 e +1 한다.
3. 만약 sum이 k와 동일하다면 (조건합격) , change_answer()을 호출하여 답을 갱신한다(갱신할 조건이라면)

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


int startIdx = -1; 
int endIdx = -1;
void change_answer(int i, int j){
    if(startIdx == -1){
        startIdx = i; 
        endIdx =j; 
        return;
    }
    if(j-i > endIdx-startIdx) return;
    if(endIdx-startIdx > j-i){
        startIdx = i; endIdx = j; return;
    }
    if(i < startIdx){
        startIdx = i; endIdx =j; return;
    }
}
vector<int> solution(vector<int> sequence, int k) {
    vector<int> answer;
    
    
    int s= 0; int e=0;
    long long sum = 0;
    for(int i=0; i<sequence.size(); i++){
        
        sum += sequence[i];
        e = i;
        
        while(sum >k && s<e){
            sum -= sequence[s];
            s++;  
        } 
        //cout << s <<","<<e<<", sum:"<<sum<<endl;
        
        if( sum < k) continue;
        else if(sum == k){
            change_answer(s,e);
        }
    }
    
    answer.push_back(startIdx);
    answer.push_back(endIdx);
    return answer;
}