[프로그래머스 level_4] 쿠키 구입 for JAVA (Summer/Winter Coding(~2018))

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

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

[문제 설명]

 

과자를 바구니 단위로 파는 가게가 있습니다. 이 가게는 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 이하인 자연수입니다.

---

입출력 예

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

입출력 예 설명

입출력 예 #1

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

 

[풀이]

- i 분기를 기준으로 왼쪽 누적 합, 오른쪽 누적 합을 비교하며 문제를 해결했다.

• i를 기준으로 i(왼쪽) i+1(오른쪽) 값을 비교하여 i값이 작다면 i -1에 해당하는 값을 i값과 합쳐주고 그 반대라면 오른쪽에 합쳐준다.
• 만약 위의 연산 결과를 통해 왼쪽 누적 합과 오른쪽 누적 합이 같다면 max값(과자 개수) 보다 큰지 작은 지를 판단하여 크면 값을 넣어준다.
• 위의 연산을 i를 분기점으로 보고, 0부터 cookie배열 길이 -1 까지 반복하여 해주면 된다.

 

[코드]

public int solution(int[] cookie) {
        int leftSum, leftIdx;
        int rightSum, rightIdx;
        int answer = 0;
        
        for(int i = 0; i < cookie.length-1; i++) {   
            leftSum =cookie[i];
            leftIdx = i;
            rightSum =cookie[i+1];
            rightIdx = i+1; 
            while(true) {
                if(leftSum == rightSum && answer < leftSum) {
                    answer = leftSum;
                }
                if(leftIdx > 0 && leftSum <= rightSum) {
                    leftIdx--;
                    leftSum += cookie[leftIdx];
                }else if(rightIdx < cookie.length-1 && leftSum >= rightSum) {
                    rightIdx++;
                    rightSum += cookie[rightIdx];
                }else {
                    break;
                }
            }
        }
        return answer;
    }