[프로그래머스, 49995] 쿠키 구입 (java)

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

프로그래머스

---

메모리: 60.4 MB, 시간: 34.83 ms

사용 알고리즘: 누적 합, 자료구조

 

 첫째 아들의 바구니 범위를 정했을 때, 해당 범위 내의 과자 수를 한 번에 구하기 위해 누적합을 sum 배열에 저장한다.

또한 첫째 아들의 과자 수가 정해졌을 때, 같은 과자 수를 가지는 범위가 있는지 한 번에 구하기 위해 누적합을 HashSet에 저장해 둔다.

 

2중 for문으로 첫째 아들의 바구니 범위를 정하고, sum 배열로 해당 범위의 과자 수를 구한다.

같은 과자 수를 가진 범위를 구하기 위해 set에 조회하고, 있다면 최댓값을 갱신한다.

import java.util.*;

class Solution {
    public int solution(int[] cookie) {
        
        // 누적합 저장
        int[] sum = new int[cookie.length + 1];
        HashSet<Integer> set = new HashSet<>();
        for(int i = 1; i <= cookie.length; i++) {
            sum[i] += sum[i - 1] + cookie[i - 1];
            set.add(sum[i]);
        }
        
        // 첫째 아들에게 줄 바구니 범위를 정하고
        // 둘째 아들에게 줄 수 있는 같은 과자 수의 바구니 범위가 있는지 확인
        int answer = 0; // 최대값
        int firstChild;
        for(int i = 0; i < cookie.length; i++) {
            for(int j = i + 1; j <= cookie.length; j++) {
                firstChild = sum[j] - sum[i]; // 첫째 아들에게 줄 바구니 범위를 정하고, 범위 안의 과자 수를 저장
                // firstChild와 같은 과자 수를 가진 바구니의 범위가 있는지 확인
                // (answer보다 과자 수가 많을 때만 검사)
                if(answer < firstChild && set.contains(sum[j] + firstChild)) {
                    answer = firstChild;
                }
                
            }
        }
        return answer;
    }
}