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

문제 : Programmers-쿠키 구입

문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

 

필요 알고리즘 개념

• 두 포인터 (투 포인터)
  
  • 투 포인터 알고리즘을 알고 있다면 어렵지 않게 풀어볼 수 있다.

 

  일반적으로 문제를 좀 더 단순화해서 생각해보면 풀이를 생각하기 쉬운 경우가 많다. 한번 m이 고정이라고 생각해보고 어떻게 풀지 생각해보자. 그렇다면 l과 r을 적절히 조정해서 l~m의 합과 m+1~r 까지의 합을 동일하게 만드는 문제가 된다. 그리고 입력값으로 0 또는 음수가 주어지지 않으므로 단순히 l~m의 합이 m+1~r의 합보다 작다면 l을 줄이고, 그 반대라면 r을 늘려주기만 하면 된다. 즉 l과 r 두개의 포인터가 있는 투 포인터 문제로 생각해볼 수 있다.

 

  그 이후로는 m을 0부터 cookie의 길이-2 까지 증가시키면서 매번 투 포인터를 사용해 양쪽이 동일하게 되게 해주면 된다. 따라서 cookie의 길이가 N이라 할 때, 투 포인터로 찾는게 O(N), m이 0부터 N-2까지 증가하는게 O(N)이므로 O(N^2)에 답을 구할 수 있다. N의 최대치는 2000이므로 별 문제없이 통과 가능하다.

 

  이하 코드에서는 try-catch를 사용했는데, 그냥 a가 0 이하로 내려가거나 b가 N이상으로 올라가는걸 따로 체크하기 귀찮아서 넣어줬다(넘어간 순간 해당 투 포인터 알고리즘 로직은 종료하면 된다.)

 

 

코드 : github

/**
 * 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges
 */
class Solution {
    public int solution(int[] cookie) {
        int answer = 0;
        for (int i = 0; i < cookie.length - 1; i++) {
            int a = i;
            int b = i+1;
            int sumA = cookie[a];
            int sumB = cookie[b];
            while (a >= 0 && b < cookie.length) {
                try {
                    if (sumA == sumB) {
                        answer = Math.max(answer, sumA);
                        sumA += cookie[--a];
                        sumB += cookie[++b];
                    } else if (sumA < sumB) {
                        sumA += cookie[--a];
                    } else {
                        sumB += cookie[++b];
                    }
                } catch (ArrayIndexOutOfBoundsException e) {
                    break;
                }
            }
        }
        return answer;
    }
}