프로그래머스 - 쿠키 구입

문제

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

프로그래머스

 

문제 풀이

 

처음에 누적합을 구한 후 l이 0~cookieSize, r이 cookieSize~l, m이 l~r 로 삼중 반복문을 사용해 풀었다. 정확성 테스트는 통과했는데 효율성 테스트에서 아무리 break를 줘도 4개의 테케가 틀려서 다시 풀었다..

 

첫 번째 방법 (효율성 틀림)

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

using namespace std;

int solution(vector<int> cookie) {
    int answer = 0;
    int cookieSize = cookie.size();
    vector<int> cookieSum(cookieSize, 0);
    
    int l, r, m;
    int leftSum, rightSum;        
    
    //각 구간별 누적합
    cookieSum[0] = cookie[0];
    for(int i=1;i<cookieSize;i++){
        cookieSum[i] = cookieSum[i-1] + cookie[i];
    }

    for(l=0; l<cookieSize; l++){
        if( answer > (cookieSum[cookieSize-1] - cookieSum[l] + cookie[l])) break;
        for(r=cookieSize-1; r>l; r--){            
            //l이 l+1 ~ r보다 크면 검사 x
            if(cookie[l] > (cookieSum[r] - cookieSum[l])) break;
            //r이 l~ r-1보다 크면 검사 x
            if(cookie[r] > (cookieSum[r-1] - cookieSum[l] + cookie[l])) continue;    
            //answer가 최대 쿠키sum보다 크면 검사 x
            if(answer > (cookieSum[r-1] - cookieSum[l] + cookie[l])) break;
            
            for(m=l; m<r; m++){                
                //left: l~m right: m+1~r
                leftSum = cookieSum[m] - cookieSum[l] + cookie[l];
                rightSum = cookieSum[r] - cookieSum[m];
                if(leftSum == rightSum){
                    answer = max(answer, leftSum);
                    if(answer == cookieSum[cookieSize-1] / 2) return answer; //최댓값
                }
            }
        }
    }
        
    return answer;
}

 

두 번째 방법

가운데 m을 0~cookieSize-1 까지 옮겨가며 left와 right의 범위를 확장해서 풀었다. 확실히 첫 번째 방법보다 훨씬 빠르다.

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

using namespace std;

int solution(vector<int> cookie) {
    int answer = 0;
    int cookieSize = cookie.size();
    int leftSum, rightSum;
    int l,r;
        
    //범위 내에서 l은 --, r은 ++만 함
    for(int i=0;i<cookieSize-1;i++){ //i가 m                
        l = i;
        r = i+1;        

        leftSum = cookie[l];
        rightSum = cookie[r];
        
        while(l >= 0 && r < cookieSize){                                    
            if(leftSum == rightSum){
                answer = max(answer, leftSum);   
                if(l-1 >= 0){
                    l--;
                    leftSum += cookie[l];
                }
                else if(r+1 <= cookieSize){
                    r++;
                    rightSum += cookie[r];
                }
                else break;
            }
            else if(leftSum < rightSum){
                if(l-1 < 0) break;
                l--;
                leftSum += cookie[l];
            }
            else if(leftSum > rightSum){
                if(r+1 >= cookieSize) break;
                r++;
                rightSum += cookie[r];
            }
        }
    }
        
    return answer;
}