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

프로그래머스

 

문제!

---

어떤 수열의 연속 부분 수열에 같은 길이의 펄스 수열을 각 원소끼리 곱하여 연속 펄스 부분 수열을 만들려 합니다. 펄스 수열이란 [1, -1, 1, -1 …] 또는 [-1, 1, -1, 1 …] 과 같이 1 또는 -1로 시작하면서 1과 -1이 번갈아 나오는 수열입니다.
예를 들어 수열 [2, 3, -6, 1, 3, -1, 2, 4]의 연속 부분 수열 [3, -6, 1]에 펄스 수열 [1, -1, 1]을 곱하면 연속 펄스 부분수열은 [3, 6, 1]이 됩니다. 또 다른 예시로 연속 부분 수열 [3, -1, 2, 4]에 펄스 수열 [-1, 1, -1, 1]을 곱하면 연속 펄스 부분수열은 [-3, -1, -2, 4]이 됩니다.
정수 수열 sequence가 매개변수로 주어질 때, 연속 펄스 부분 수열의 합 중 가장 큰 것을 return 하도록 solution 함수를 완성해주세요.

---

요약하면 [-1 1 -1 1 ...] 배열과 [1 -1 1 -1 ...] 배열들을 곱해서 최대가 되는 부분수열을 구하는 문제입니다.

 

문제 길이가 짧은 만큼 생각난 방법이 없어 문제대로 풀기 시작했습니다.

 

일단 두 배열에 맞는 부분합을 계산해 주었습니다.

그리고 틀려버렸습니다...

 

 

 

 

틀린부분을 보자면

 

먼저 두 배열을 따로 만들어 주고

sum_m.push_back(sequence[0]*-1);
    sum_p.push_back(sequence[0]);
    
    for(int i=1;i<sequence.size();i++){
        if(i%2==1){
            sum_m.push_back(sequence[i]+sum_m.back());
            sum_p.push_back(sequence[i]*-1+sum_p.back());
        }
        else{
            sum_m.push_back(sequence[i]*-1+sum_m.back());
            sum_p.push_back(sequence[i]+sum_p.back());
        }
    }

 

부분합 비교를 통해 풀어주었으나 17 18 19 20 에서 시간초과가 나네요...

 

 for(int i=0;i<sequence.size();i++){ // 부분합 비교
        answer=max(answer,sum_m[i]);
        answer=max(answer,sum_p[i]);
        for(int j=i+1;j<sequence.size();j++){
            answer=max(answer,sum_m[j]-sum_m[i]);
            answer=max(answer,sum_p[j]-sum_p[i]);
        }
    }

 

여기서 좀 더 나가서  부분합의 시작점이  마이너스인 부분을 제외하는 코드를 짜보았지만.. 

 

if(i!=0){  // 현재 위치 숫자 ㅇㅇ
            temp_p=sum_p[i]-sum_p[i-1];
            temp_m=sum_m[i]-sum_m[i-1];
        }
        else{
            temp_m=sum_m[0];
            temp_p=sum_p[0];
        }
        
        if(temp_p<0){ // 방향 설정 /// m부분만 실행할것
            dir=false;
        }
        else{
            dir=true;
        }
        
        ......
        
        if(dir){
            answer=max(answer,sum_m[j]-sum_m[i]);
        }
        else{
            answer=max(answer,sum_p[j]-sum_p[i]);
        }

 

실행시간은 줄어드는데 여전히 시간초과나네요..

 

 

 

 

단순 부분합 문제가 아닌것 같습니다...

 

 

 

 

But! 여기서 좀 더 제외 시킬수 있는 부분을 생각해 보았습니다. 

 

현재 부분합으로 계산중인데 만약 

[2 -3 -6 1 3] 이라는 배열이 있을때 이걸 부분합으로 보면

[2 -1 -7 -6 -3] 입니다.   >>>>>>> 이부분에서 약간의 힌트를 찾을수 있었습니다...

 

만약 전 단계까지의 부분합이 마이너스인 경우!

현재 숫자가 + (양수)가 나올경우 앞단계를 생각해줄 필요가 없는것 이였습니다! 

 

약간 부분합이 아닌 문제에 맞게 바꾸어보면

[2 -1 -7 (이부분에서 손절..) 1 4] 이런식으로 바꿀수 있었습니다.

그러면 위 배열의 최댓값은 4! 굳굳 

 

 

이런식을 만들어 보면

for(int j=i+1;j<sequence.size();j++){
            
            if(dir){
                if(sum_m[j]-sum_m[i]<0){
                    break;
                }
                answer=max(answer,sum_m[j]-sum_m[i]);
            }
            else{
                if(sum_p[j]-sum_p[i]<0){
                    break;
                }
                answer=max(answer,sum_p[j]-sum_p[i]);
            }
        }

이런식으로 나누어 처리해주면? 끝!

 

부분합이 마이너스가 되는데도 계속해서 탐색해주는 부분때문에 시간초과가 생기는 거였네요.... 

 

 

 

 

ALL (좀 길어졌네요... 시작점 / 방향설정하는 부분에서 좀 더 줄일수 있을거 같습니다!)

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

using namespace std;

vector<long long> sum_m; // -1 1 -1 1
vector<long long> sum_p; // 1 -1 1 -1

long long solution(vector<int> sequence) {
    long long answer = -9999999;
    
    sum_m.push_back(sequence[0]*-1);
    sum_p.push_back(sequence[0]);
    
    for(int i=1;i<sequence.size();i++){
        if(i%2==1){
            sum_m.push_back(sequence[i]+sum_m.back());
            sum_p.push_back(sequence[i]*-1+sum_p.back());
        }
        else{
            sum_m.push_back(sequence[i]*-1+sum_m.back());
            sum_p.push_back(sequence[i]+sum_p.back());
        }
    }
    
    bool dir=false;
    
    for(int i=0;i<sequence.size();i++){ // 부분합 비교
        answer=max(answer,sum_m[i]);
        answer=max(answer,sum_p[i]);
        
        int temp_p=0,temp_m=0;
        
        if(i!=0){  // 현재 위치 숫자 ㅇㅇ
            temp_p=sum_p[i]-sum_p[i-1];
            temp_m=sum_m[i]-sum_m[i-1];
        }
        else{
            temp_m=sum_m[0];
            temp_p=sum_p[0];
        }
        
        
        if(temp_p<0){ // 방향 설정 /// m부분만 실행할것
            dir=false;
        }
        else{
            dir=true;
        }
        
        for(int j=i+1;j<sequence.size();j++){
            
            if(dir){
                if(sum_m[j]-sum_m[i]<0){
                    break;
                }
                answer=max(answer,sum_m[j]-sum_m[i]);
            }
            else{
                if(sum_p[j]-sum_p[i]<0){
                    break;
                }
                answer=max(answer,sum_p[j]-sum_p[i]);
            }
        }
    }
    
    
    
    
    return answer;
}

 

 

 

 

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