[프로그래머스/C++] 쿠키 구입

 

 

문제

문제 설명

 

 

 

풀이

 

[풀이]

 

쿠키의 길이가 최대 2000이기 때문에 시작점과 끝 점을 고르면 이분탐색으로 절반으로 나눌 수 있는지 쉽게 구할 수 있다고 생각했다.

 

그리고 계속 반복해서 시작점과 끝점을 더하는 계산이 나오지 않도록 부분합을 이용해 반복 덧셈을 줄였다.

 

쿠키의 시작점과 끝점이 주어지면 먼저 쿠키의 개수의 총합이 홀수인지 짝수인지 확인한다. 홀수인 경우는 절반으로 나눌 수 없으므로 패스한다.

짝수일 경우는 이분탐색으로 쿠키를 절반으로 나눌 수 있는지 탐색하면 된다.

​

[아이디어 정리]

1. 쿠키의 부분합을 구한다. (반복 덧셈을 줄이기 위해서)
2. 시작점과 끝점을 기준으로 이분탐색을 해 쿠키를 절반으로 나눌 수 있는지 구한다.
3. 쿠키를 절반으로 나눌 수 있는 경우 중 가장 많은 쿠키인 경우를 return한다.

 

 

Code

 

 

#include <string>
#include <vector>

using namespace std;

vector<int> realCookie;

int binarySearch(int st, int ed, int targetNum)
{
    int defaultNum=realCookie[st-1];
    int mid=0;
    int cpNum;
    while(st<=ed)
    {
        mid = (st+ed)/2;
        cpNum=realCookie[mid]-defaultNum;
        if (cpNum==targetNum)
        {
            return targetNum;
        }
        else if (cpNum>targetNum)
        {
            ed=mid-1;
        }
        else
        {
            st=mid+1;
        }
    }
    return 0;
}

int solution(vector<int> cookie) {
    int answer = 0;
    int a=0;
    int b;
    realCookie.push_back(0);
    for (int i=0; i<cookie.size(); i++)
    {
        a+=cookie[i];
        realCookie.push_back(a);
    }
    for (int l=1; l<realCookie.size(); l++)
    {
        for (int r=l+1; r<realCookie.size(); r++)
        {
            
            b=realCookie[r]-realCookie[l-1];
            if (b%2==0)
            {
                // 이분탐색 코드
                a=binarySearch(l, r, b/2);
                if (a>answer)
                {
                    answer=a;
                }
            }            
        }
    } 
    
    return answer;
}

 

---

 

 

시간을 줄이려면 양끝에서 탐색을 시작하면 절반으로 나눌 수 있을 때 바로 return 해 속도를 빠르게 할 수도 있다

어차피 쿠키의 길이가 길수록 최대값이 나오기 때문이다

 

프로그래머스