[프로그래머스 Level.4] 쿠키 구입 (Summer/Winter Coding(~2018)) (Java)

문제 링크

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

프로그래머스

 

 

 

코딩테스트 연습 > Summer/Winter Coding(~2018) > 쿠키 구입

 

 

 

문제 설명

 

 

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

 

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

 

 

 

 

나의 코드

import java.util.*;

class Solution {
    public int solution(int[] cookie) {
        int answer = 0;
        
        for(int i=0; i<cookie.length-1; i++) {
            int left = i;
            int right = i+1;
            int leftSum = cookie[left--];
            int rightSum = cookie[right++];
            
            while(true) {
                // System.out.println("i = "+i+ " /  left = "+(left+1)+" / right = "+(right-1)+" / leftSum = "+leftSum+" / rightSum = "+rightSum);
                
                if(leftSum == rightSum) {
                    answer = Math.max(answer, leftSum);
                }
                
                if(leftSum >= rightSum && right <= cookie.length-1) {
                    rightSum += cookie[right++];
                } else if(leftSum <= rightSum && left >= 0) {
                    leftSum += cookie[left--];
                } else {
                    break;
                }
                
            }
        }
        
        return answer;
    }
}

 

풀이

1. 투포인터로 두 지점을 잡고 위치를 변경시켜주면서 옳은 지점을 찾아 최대값을 갱신시켜주면서 문제를 풀었다.
2. 투포인터로 인덱스를 left=i, right=i+1로 잡고 조건에 따라 left는 i지점부터 왼쪽(인덱스 -1씩)으로 이동하고 right는 인덱스를 오른쪽(인덱스 +1씩)으로 이동해간다. 
3. right가 i+1부터이므로 cookie.length-1만큼 for문을 돌려주면서 해당 i를 기준으로 인덱스의 위치 left와 right, left와 right의 누적 합을 구할 int형 변수 leftSum과 rightSum을 선언한다.
4. while문을 돌면서 leftSum과 rightSum이 같으면 최대값인지 확인하여 갱신시켜준다.
5. leftSum이 rightSum보다 같거나 크고 right가 오른쪽으로 더 이동할 인덱스가 남아있다면 right를 이동시킨다.
6. rightSum이 leftSum보다 같거나 크고 left가 왼쪽으로 더 이동할 인덱스가 남아있다면 left를 이동시킨다.
7. rightSum이 leftSum보다 작은데 right가 이동할 인덱스가 남아있지 않거나 leftSum이 rightSum보다 작은데 left가 이동할 인덱스가 남아있지 않다면 while문을 종료시키면 된다.
8. 결론은 leftSum과 rightSum를 비교하여 작은 쪽을 인덱스 증가시켜주고 해당 인덱스의 수를 더해가면 된다.
    leftSum과 rightSum이 같다면 어차피 어느쪽을 움직여도 상관없다. (움직인 쪽이 더 커지기 때문에 반대 쪽도 다음 턴데 바로 움직일 것이기 때문이다.)