Q 2003 수들의 합

💡 문제 요약 및 분석

A[n] 배열에서 A[i] + A[i+1] + … + A[j-1] + A[j] = M 이 되는 경우의 수를 모두 찾아라.

💡 알고리즘 설계

✅ 누적합 + map 을 활용하자.

1. 입력

   • 표준입력으로 N개만큼 입력 받으면서 누적합 배열 prefix[] 를 생성

2. 연산

   • 문제에서 주어진 조건은 prefix[j] - prefix[i] = M 이므로, prefix[j] - M = prefix[i] 라는 공식으로 풀어낼 수 있다.
   • 계산 결과를 저장하기 위한 map 을 만들고 put(0,1) 한다. (0번째 인덱스는 for문 범위에 들어가지 않기 때문에 미리 추가함)
   • for문으로 prefix[n] 까지 반복하면서 prefix[n] - M 의 결과가 map 에 있으면 count 한다.
   • prefix[n] 을 map 에 key 로 등록한다. (만약 이전에도 prefix[n] 이 있었을 경우를 감안해서 value 는 누적해서 저장한다.)

3. 출력

   • count 변수를 출력한다.

💡 코드

import java.util.*;

public class Main {

    static int read() throws Exception {
        int c, n = 0;
        while ((c = System.in.read()) > 47) n = (n << 3) + (n << 1) + (c & 15);
        return n;
    }

    public static void main(String[] args) throws Exception {
        int n = read();
        int m = read();
        int[] prefix = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            prefix[i] = prefix[i-1] + read();
        }

        int count = 0;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0,1);
        for (int i = 1; i <= n; i++) {
            count += map.getOrDefault((prefix[i] - m), 0);
            map.put(prefix[i],map.getOrDefault(prefix[i],0) + 1);
        }
        System.out.println(count);
    }

}

💡 시간 복잡도, 공간 복잡도

시간 복잡도	공간 복잡도
O(n)	O(n)

💡 다른 풀이

연산 과정을 보니 굳이 prefix 배열을 만들 필요는 없을 것 같다. 표준입력 받는 값을 누적합하면서 연산하는 과정으로 바꿔봤다. 시간 복잡도 면에서 보면 큰 차이는 없지만 n+1 크기의 배열이 사라졌으니 그만큼 공간 복잡도가 감소할 것이다. (여기서는 n의 크기가 크지 않으므로 미미하긴 하다…)

import java.util.*;

public class Main {

    static int read() throws Exception {
        int c, n = 0;
        while ((c = System.in.read()) > 47) n = (n << 3) + (n << 1) + (c & 15);
        return n;
    }

    public static void main(String[] args) throws Exception {
        int n = read();
        int m = read();

        int sum = 0; // 누적합하는 변수
        int count = 0; // 경우의 수 집계

        Map<Integer, Integer> map = new HashMap<>();
        map.put(sum,1);
        for (int i = 1; i <= n; i++) {
            sum += read();
            count += map.getOrDefault((sum - m), 0);
            map.put(sum,map.getOrDefault(sum,0) + 1);
        }
        System.out.println(count);
    }

}