Programmers 문제 49995번 쿠키 구입

문제 출처:https://programmers.co.kr/learn/courses/30/lessons/49995

코딩테스트 연습 - 쿠키 구입

Programmers 49995번 문제 쿠키 구입

 

---

문제 분석

일렬로 나열된 쿠키 바구니를 2명의 아들에게 똑같이 나누어 주기위해 구매하고자 합니다. 다만 구매를 할때에는 이어진 바구니들만 구매를 할 수 있으며, 각 바구니 안에 들어 있는 쿠키의 개수가 인풋으로 주어집니다. 나누어 줄 수 있는 쿠키의 최대 개수를 구하는 문제입니다. 제일 처음으로 집게되는 바구니를 pivot으로 지정하겠습니다.

저는 이 문제를 해결하기 위해 다음과 같은 알고리즘을 구상했습니다: 

1. 바구니의 개수만큼 loop를 돌아 pivot을 정합니다.                                                 O(n)
2. pivot을 첫째 아들에게 주고 첫째 아들이 가진 쿠키의 개수를 업데이트합니다.
3. 현재 보고있는 쿠키 바구니 양 옆에 남아있는 쿠키 바구니들을 살펴봅니다.                 O(n-1) -- worst case 
   1. 두 아들들이 가진 쿠키의 개수를 비교하여 같다면, 최대값을 저장합니다.
   2. 다르다면 더 개수가 작은 쪽으로 바구니를 1개 더 구입합니다. 아들에게 줍니다.(update)
   3. 쿠키 바구니가 모자를 때까지 반복합니다.

시간 복잡도 ${O(n^2)}$으로 구할 수 있었습니다.

---

코드는 다음과 같습니다:

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> cookie) {
    int answer = 0;
    for(int i = 0 ; i < cookie.size()-1 ; i++){
        int left_idx = i, right_idx = i + 1 ;
        int left_sum = cookie[left_idx], right_sum = cookie[right_idx] ;
        
        while(0 <= left_idx && right_idx < cookie.size()){
            if(left_sum == right_sum)
                answer = max(answer, left_sum) ;
            
            if(left_sum < right_sum)
                left_sum += cookie[--left_idx] ;
            else
                right_sum += cookie[++right_idx] ;
        }
    }
    return answer;
}

해당 문제는 Github에서도 보실 수 있습니다:

https://github.com/gurcks8989/CodingTest/blob/master/Programmers/P49995_Buy_Cookie.cpp

GitHub - gurcks8989/CodingTest: CodingTest_study_with_c++

훈수 및 조언은 언제든 환영입니다.