[Java/투포인터, 누적합] 코드트리. 바구니 안의 사탕

 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

🤔 Intuition

직관적으로 떠오른 풀이는 누적합을 이용한 슬라이딩 윈도우였다. 구간의 사이즈가 고정되어있기 때문이다.

하지만 역시나 슬라이딩 윈도우는 투포인터로도 풀 수 있다. 두 알고리즘 모두 알고리즘 자체 시간복잡도는 O(N) 일 테니 소요 시간은 비슷할 것으로 예상했다.

🔎 Algorithm & Complexity

* @algorithm two pointer
* @time O(N) -> 729 ms
* @memory O(N) -> 38 MB

* @algorithm prefix sum
* @time O(N) -> 808 ms
* @memory O(N) -> 47 MB

👨🏻‍💻 Logic

투포인터는 hashmap을 이용하여 정렬 없이 각 좌표에 대한 구간합을 구할 수 있었다. 투포인터 로직은 인덱스를 이용하여 각 좌표에 대한 값을 직접 조회하면서 구간합을 구하는 방식이라 별도 배열을 추가하지 않고 해시맵만을 이용하므로 메모리 활용 측면에서 효율적이다. 따라서 이 문제에서 굳이 최적의 풀이를 꼽자면 누적합보단 투포인터임을 알 수 있다.

public class CodeTree_바구니안의사탕_투포인터 {
    private static int N, K;
    private static final int basketSize = 1_000_000;
    private static HashMap<Integer, Integer> hm = new HashMap<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int candy = Integer.parseInt(st.nextToken());
            int pos = Integer.parseInt(st.nextToken());
            hm.put(pos, hm.getOrDefault(pos, 0) + candy);
        }

        int max = 0;
        int sum = 0;
        int j = 0;
        for (int i = 0; i <= basketSize; i++) {
            while (j <= basketSize && j - i + 1 <= 2 * K + 1) {
                sum += hm.getOrDefault(j, 0);
                j++;
            }
            // 구간 설정 완료
            max = Math.max(sum, max);
            sum -= hm.getOrDefault(i, 0);
        }
        System.out.println(max);

        br.close();
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

 

하지만 직관적으로 구간의 크기가 일정하다면 슬라이딩윈도우 & 누적합을 떠올리는게 일반적이기 때문에, 일단 이 방식으로도 구현해 보았다. 주의할 점은, x의 범위가 0까지 고려되어야 하고, K의 최대가 2백만이므로 1백만을 넘을 때에는 누적합 배열의 끝 인덱스 값을 반환하는 것을 추가해줘야 한다.

public class CodeTree_바구니안의사탕_누적합 {
    private static int N, K;
    private static HashMap<Integer, Integer> hm = new HashMap<>();
    private static long[] ps = new long[1_000_000 + 1];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            int c = Integer.parseInt(st.nextToken()); // candy count
            int p = Integer.parseInt(st.nextToken()); // candy position
            hm.put(p, hm.getOrDefault(p, 0) + c);
        }

        long num = 0;
        for (int i = 0; i <= 1_000_000; i++) {
            if (hm.containsKey(i)) {
                num += hm.get(i);
            }
            ps[i] = num;
        }

        long max = 0;
        if (K >= 1_000_000) {
            max = ps[1_000_000];
        } else {
            for (int i = 1; i <= 1_000_000; i++) {
                if (i > K && i + K <= 1_000_000) {
                    max = Math.max(max, ps[i + K] - ps[i - K - 1]);
                }
            }
        }

        sb.append(max);
        br.close();
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}