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

 

 

---

 

 

온라인 문제풀이 사이트 Programmers의 문제인 '쿠키 구입' 문제.

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

 

문제는 간단하게 다음과 같다.

1. 정수형 1차원 배열(각 바구니 당 사탕의 개수)이 주어진다.

2. 두 아들에게 같은 양의 쿠키를 선물하려 한다.

3. 첫 번째 아들에게 a번째 ~ b번째 바구니, 두 번째 아들에게 b+1번째 ~ c번째 바구니를 골라 선물한다.

4. 이 때, (a ~ b)의 양 = (b+1 ~ c)의 양이어야 한다.

5. 선물할 수 있는 쿠키의 최대 개수를 구한다.

 

.

원 안의 숫자는 각 바구니에 있는 쿠키의 개수이며,
첫 번째 아들에게 2, 3번째 바구니를, 두 번째 아들에게 마지막 바구니를 선물하면 각각 3개로
선물할 수 있는 최댓값이 된다

 

풀이 과정

가장 먼저 떠오른 방법은 역시 dynamic programming 이었다.

임의의 지점(a)부터 b까지 쿠키의 합을 구해야 하고, 정답은 최댓값이기 때문에 무작정 dp로 덤볐다.

그러나 점화식을 세우는 과정에서 문제가 발생했다.

현재 i번 째 index를 검사 중이라면, dp[i] - dp[i-1] ~ dp[i] - dp[1], 그리고 cookie[i+1] ~ cookie[N-1] 구간의 dp 값을 동시에 계산해야 해서 반복문의 개수가 늘어날 위험성이 있었다.

그렇다고 재귀를 적용하기에는 분명 효율성에서 불리할 것으로 보였다.

 

그런데 자세히 보니, i번 째 index에서 양 옆으로 값을 더하며 비교하다 보면, 생각보다 빠르게 일치하는 값을 찾아낼 수 있을 것 같았다.

중요한 조건은 값을 더하다가도 비교 대상보다 값이 커지면 이 조합은 같은 양의 쿠키가 될 수 없기 때문에 불필요한 계산을 덜어낼 수 있다는 점이다.

 

아래는 코드 전문

public static int solution(int[] cookie) {
        int answer = -1;
        int max = 0;
        
        if(cookie.length < 2) return 0;
        if(cookie.length == 2) {
            if(cookie[0] == cookie[1]) return cookie[0];
            else return 0;
        }
        
        for(int i = 0; i < cookie.length - 1; i++) {
            
            int frontSum = cookie[i];
            int indexOfFrontSum = i;
            
            int backSum = cookie[i+1];
            int indexOfBackSum = i+1;
            
            while(true) {
 
                if(frontSum == backSum) max = Math.max(frontSum, max);
                
                if(indexOfFrontSum > 0 && frontSum <= backSum) {
                    indexOfFrontSum--;
                    frontSum += cookie[indexOfFrontSum];
                }
                
                else if(indexOfBackSum < cookie.length - 1 && frontSum >= backSum) {
                    indexOfBackSum++;
                    backSum += cookie[indexOfBackSum];
                }
                
                else break;
            }
            
        }
        
        answer = max;
        return answer;
    }

복잡한 알고리즘보다는 어떻게 효율적으로 값을 찾아낼 수 있는지, 어떻게 조건을 분기할 지를 중심으로 신중히 생각하면 해결할 수 있는 문제였다.