[프로그래머스] 연속된 부분 수열의 합

문제

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

1차 시도

접근 방법

누적합 이용
// 수열의 개수가 1인 경우
// prefix[1] - prefix[0] = 1 - 0 = 1
// prefix[2] - prefix[1] = 1+2 - 1 = 2
//..
// size = 5
// prefix[size] - prefix[size-1] = 1+2+3+4+5 - 1+2+3+4
// 수열의 개수가 2인 경우
// prefix[2] - prefix[0] = 1+2 - 0 - 1
// prefix[3] - prefix[1] = 1+2+3 - 1
// prefix[4] - prefix[2] = 1+2+3+4+ - 1+2 = 7
//..
// size = 5
// prefix[size] - prefix[size-2] = 1+2+3+4+5 - 1
// 수열의 개수가 3인 경우
// prefix[4] - prefix[1] = 1+2+3+4 - 1 =
// 수열의 개수가 size인경우
// prefix[size] - prefix[size-size] = 1+2+3+4+5 - 0

풀이

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

using namespace std;

int prefix[1000004];

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

    // 누적합 만들기
    for(int i=0; i<sequence.size(); i++)
    {
        prefix[i+1] = prefix[i] + sequence[i];
    }
    
    // 수열의 개수 1 ~ 시퀀스 길이만큼 for문
    
    // 백만 * 백만 -> 에바 
    for (int i=1; i<=sequence.size(); i++)
    {
        for(int j=i; j<=sequence.size(); j++)
        {
            if (prefix[j] - prefix[j-i] == k)
            {
                answer.push_back(j-i);
                answer.push_back(j-1);
                return answer;
            }
        }
    }
    

    
    return answer;
}

결과

당연하게도... 시간초과

2차 시도

접근 방법

[투포인터]
1. left와 right 인덱스를 지정해주고 left부터 right 전까지의 부분 수열의 합을 sum이라 가정하자
2. 구해야하는 합 k보다 작다면 right를 오른쪽으로 이동해서 sum의 크기를 키워주고
3. 구해야하는 k보다 크다면 left를 오른쪽으로 이동해서 sum의 크기를 줄여주고
4. sum이 k와 같다면 left부터 right까지의 길이가 기존에 구한 left부터 right의 길이보다 짧다면 새롭게 갱신해 주면 되는 문제다.

풀이

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

using namespace std;


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

   int cnt = 0;
   int diff = 1000004;
   
   int sum = sequence[0];
   int left = 0; 
   int right = 1;
   while(left < right)
   {    
       if (sum == k)
       {
           if ((right-1) - left < diff)
           {
               answer.clear();
               answer.push_back(left);
               answer.push_back(right-1);
               diff = (right-1) - left;
           }       
           sum -= sequence[left++];   
       }
       else if (sum > k)
           sum -= sequence[left++];
       else if (right < sequence.size())
           sum += sequence[right++];
       else 
           break;
   
   }
   
   return answer;
}

정리

아직 학습이 더 필요한

참고 블로그

[프로그래머스] 연속된 부분 수열의 합 Lv2 JAVA [투포인터][엄탱]