[프로그래머스] 쿠키 구입

https://programmers.co.kr/learn/courses/30/lessons/49995?language=java 

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

 

기준점 m 을 잡고 i 는 왼쪽으로, r 은 오른쪽으로 이동하면서 합한 과자의 수를 비교하였다.

 

cookie = {1, 1, 2, 3} 을 예로 들 때, m 은 둘째 아들에게 줄 수 있는 바구니 중 가장 작은 번호로 기준을 잡았기 때문에 1번부터 시작한다.

 

fir = cookie[m - 1], sec = cookie[m] 으로 시작하여

1) fir < sec 이면 i 를 감소시켜 fir += cookie[i]

2) fir > sec 이면 r 를 증가시켜 sec += cookie[r]

3) fir == sec 이면 answer 을 최댓값(= fir) 으로 갱신시켜 주고 r 을 증가, i 를 감소시켜준다.

 

이동할 수 없다면(i == 0 or  r == cookie.length - 1) break 로 다음 기준점 m 을 잡는다.

 

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 fir = cookie[i];
            int sec = cookie[r];
            
            while (true) {
                if (fir == sec) {
                    if (answer < fir) answer = fir;
                }
                
                if (fir <= sec && i > 0) {
                    i --;
                    fir += cookie[i];
                } else {
                    if (fir >= sec && r < cookie.length - 1) {
                        r ++;
                        sec += cookie[r];
                    } else break; 
                } 
            }
        }
        
        return answer;
    }
}