[Java] Summer/Winter coding(쿠키 구입)

 

문제 설명

---

과자를 바구니 단위로 파는 가게가 있습니다. 이 가게는 1번부터 N번까지 차례로 번호가 붙은 바구니 N개가 일렬로 나열해 놨습니다.

철수는 두 아들에게 줄 과자를 사려합니다. 첫째 아들에게는 l번 바구니부터 m번 바구니까지, 둘째 아들에게는 m+1번 바구니부터 r번 바구니까지를 주려합니다. 단, 두 아들이 받을 과자 수는 같아야 합니다(1 <= l <= m, m+1 <= r <= N). 즉, A[i] 를 i번 바구니에 들어있는 과자 수라고 했을 때, A[l]+..+A[m] = A[m+1]+..+A[r] 를 만족해야 합니다.

각 바구니 안에 들은 과자 수가 차례로 들은 배열 cookie가 주어질 때, 조건에 맞게 과자를 살 경우 한 명의 아들에게 줄 수 있는 가장 많은 과자 수를 return 하는 solution 함수를 완성해주세요. (단, 조건에 맞게 과자를 구매할 수 없다면 0을 return 합니다)

제한사항

• cookie의 길이는 1 이상 2,000 이하입니다.
• cookie의 각각의 원소는 1 이상 500 이하인 자연수입니다.

---

입출력 예

cookieresult

[1,1,2,3]	3
[1,2,4,5]	0

입출력 예 설명

입출력 예 #1

첫째 아들에게 2, 3번 바구니를, 둘째 아들에게 4번 바구니를 사주면 두 아들은 각각 과자 3개를 받습니다.

입출력 예 #2

주어진 조건에 맞게 과자를 살 방법이 없습니다.

 

접근 방법

---

 문제를 읽고 부분합과 동적계획법을 사용한 풀이가 떠올랐으나 효율성을 통과하지 못했습니다. 하지만 투포인터를 사용하여 간단하게 해결할 수 있었습니다. 

 

1. mid가 고정된 상태에서 left와 right를 mid로 부터 1칸씩 멀어지게 적절히 조정합니다. 

(left와 right를 한 칸씩 조정하면서 합을 구할 수 있기 때문에 prefix sum은 필요없습니다.)

2. leftSum과 rightSum이 같아질 경우 answer를 최대값으로 갱신합니다.

(leftSum은 left ~ mid의 합, rightSum은 mid + 1 ~ right의 합)

3. leftSum이 더욱 클 경우 right를 mid로 부터 1칸 멀어지게 하고, rightSum이 더욱 클 경우 left를 mid로 부터 1칸 멀어지게 합니다. 

4. mid를 0~cookie.length까지 움직이며 1,2,3을 반복합니다.

 

그림으로 설명하면 아래와 같습니다.

 

소스 코드

---

class Solution {
    public int solution(int[] cookie) {
        
        int answer = 0;
        
        //4번 과정
        for(int mid = 0;mid<cookie.length - 1;mid++){
            
            int left = mid;
            int right = mid + 1;
            int lSum = cookie[mid];
            int rSum = cookie[mid+1];
            
            while(true){
                
                //2번 과정
                if(lSum == rSum){
                    answer = Math.max(answer, rSum);
                    if(++right < cookie.length) rSum += cookie[right];
                    else break;
                }
                else if(lSum > rSum){ //3번 과정
                    if(++right < cookie.length) rSum += cookie[right];
                    else break;
                }
                else{ //3번 과정
                    if(--left >= 0) lSum += cookie[left];
                    else break;
                }
            }
        }
        return answer;
    }
}