문제

풀이

1. 2중 for 문과 누적합 배열을 통해 해결해보려 하였는데 cookie의 사이즈가 최대 2천이므로 시간초과가 날것이 분명했다.

2. 그다음 생각한 방법은 이분탐색이었다. 다만 cookie 배열 내의 값은 정렬이 되지 않은 형태라 이분탐색을 바로 적용할 수 없었다.

3. 하지만 누적합 배열은 인덱스에 따라 값이 점점 커지기 때문에 이분 탐색을 적용할 수 있으리라 생각했다. 2중 반복문을 통해 부분 배열의 범위를 정해주고, 부분 배열 내에서 이분 탐색을 통해 좌우의 값이 같아지는 인덱스 값을 찾아냈다.

코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int can(int sumArr[], int start,int end){
    int l=start,r=end+1;
    while(l+1!=r){
        int mid = (l+r)/2;
        if(sumArr[mid]-sumArr[start-1] > sumArr[end]-sumArr[mid]) r=mid;
        else l=mid;
    }
    if(sumArr[l]-sumArr[start-1] == sumArr[end] - sumArr[l]) return sumArr[l]-sumArr[start-1];
    return 0;
}

int solution(vector<int> cookie) {
    int answer=0;
    int sumArr[2001];
    fill(sumArr,sumArr+2001,0);
    sumArr[1]=cookie[0];
    for(int i=2;i<=cookie.size();i++) sumArr[i] = sumArr[i-1]+cookie[i-1];
    
    for(int i=0;i<cookie.size();i++){
        for(int j=i+1;j<cookie.size();j++){
            answer = max(answer,can(sumArr,i+1,j+1));
        }
    }
    return answer;
}

후기

코딩 테스트에서 IDE 사용을 금지하는 곳이 많아져 요즘은 IDE 없이 풀어보는 중이다. 시간은 좀 더 걸리지만 처음 IDE 없이 풀이 했을 때보다 점점 시간이 단축되는게 느껴진다.