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

문제

문제 설명

 

풀이

 

[풀이]

 

처음에는 길이가 1000인 줄 알고 for 문을 두번 돌려서 빠르게 풀려고 했다. 근데 알고보니 길이가 1,000,000이여서 투포인터를 이용해 문제를 풀었다.

 

먼저 주어진 수열 대신

0번 idx에는 0,

1번 idx에는 기존 수열의 0~0 idx까지의 합

2번 idx에는 기존 수열의 0~1 idx까지의 합을 저장하는 새로운 수열 newSeq를 만들었다.

​

이후 ed를 1, st를 0으로 시작해

newSeq[ed]-newSeq[st]의 값이 k보다 작으면 ed의 값을 1 늘리고,

newSeq[ed]-newSeq[st]의 값이 k보다 크면 st의 값을 1늘렸다.

 

만약 newSeq[ed]-newSeq[st]의 값이 k와 같다면 이전에 저장한 수열의 길이보다 짧은지 확인하고 짧다면 저장하도록 했다.

 

 

Code

 

 

#include <string>
#include <vector>
using namespace std;
vector<int> solution(vector<int> sequence, int k) {
    int a=0;
    int st=0; int ed=1;
    int reSt=0; int reEd=1000001;
    int len=0;
    bool flag=false;
    vector<int> newSeq(1,0);   
    vector<int> answer;
    for (int i =0; i<sequence.size(); i++)
    {
        a+=sequence[i];
        newSeq.push_back(a);    
    }    
    while(ed<newSeq.size())
    {   
        if (newSeq[ed]-newSeq[st]==k)
        {
            if (reEd-reSt>ed-st)
            {
                reEd=ed;
                reSt=st;
            }
            st+=1;
            ed+=1;
        }
        else if(newSeq[ed]-newSeq[st]>k)
        {
            st+=1;
        }
        else
        {
            ed+=1;
        }
    }
    answer.push_back(reSt);
    answer.push_back(reEd-1);
    return answer;
}

---

 

숫자를 잘못 보고 범위를 짧게 잡았다가 하마터면 고생할 뻔 했다;;

빨리 찾아서 다행...

 

프로그래머스