프로그래머스 - 쿠키 구입(Java, 자바)

문제 링크

문제 설명

과자를 바구니 단위로 파는 가게가 있습니다. 이 가게는 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개를 받습니다.

입출력 예 #2

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

---

문제 풀이 방법

문제만 읽으면 약간 복잡해 보이는 느낌이 드는 문제인데, 단순하게 모든 범위를 거치면서 가장 큰 수만 구하면 된다.

제일 처음 상태는 위와 같게 된다.
이때 왼쪽과 오른쪽의 합이 같기 때문에 결과값에 우선 저장해준다.

양쪽의 합이 같을 때는 왼쪽 인덱스값을 -1을 해준다.
이 경우에는 index 범위에 넘어가므로 반복문을 종료한 뒤 기준이 되는 중간 인덱스를 +1 해준다.

이때는 왼쪽이 오른쪽값 보다 작다.

이럴때는 왼쪽 인덱스를 -1 해서 더 할 값을 추가로 만든다.
이때 양쪽의 값이 같기 때문에 결과값에 넣어 더 큰수를 answer 에 넣는다.

다시 또 위와 같은 과정을 반복해서 answer에 더 큰수가 들어 가게 된다.

양쪽값이 같을 때 왼쪽 인덱스를 -1을 해서 추가로 값을 더 했었다.
이때 왼쪽 값이 더 크기 때문에 오른쪽 인덱스를 증가하였다.
하지만 이때 배열 인덱스 범위를 넘기 때문에 종료가 된다.

 

여기서 포인트!

1. 양쪽의 기준이 되는 m 을 설정해두고 왼쪽, 오른쪽을 가르키는 투포인터를 사용한다.
2. 양쪽값이 같을 때 Math.max()를 사용하여 큰값을 계속 업데이트 한다.
3. 양쪽값이 같거나 왼쪽값이 더 작을 때 왼쪽 인덱스를 감소시켜 추가로 값을 더 더한다.
4. 오른쪽 값이 더 작을 때는 오른쪽 인덱스를 증가시켜 추가로 값을 더 더한다.

---

전체 코드

class Solution {
    public int solution(int[] cookie) {
        int answer = 0;

        for (int m = 1; m < cookie.length; m++) {
            int i = m - 1;
            int r = m;
            int left = cookie[i];
            int right = cookie[r];

            while (true) {
                if (left == right) {
                    answer = Math.max(answer, left);
                }

                if (left <= right && i > 0) {
                    i --;
                    left += cookie[i];
                } else if (left >= right && r < cookie.length - 1) {
                    r ++;
                    right += cookie[r];
                } else break;
            }
        }

        return answer;
    }
}