백준 2143번 : 두 배열의 합 [자바]

 

 

 

🧫 문제 분석

 

✔️ 출처

두 배열의 합 골드 3

 

📖 문제

 

누적합 + HashMap 문제

 

부 배열은 연속된 i~j까지의 합을 의미한다. 

A와 B의 부배열의 합이 T가 되는 쌍의 개수를 구한다.

 

A배열에서 나올 수 있는 모든 누적합을 구하고, (key : 누적합, value : 개수)로 해시 맵에 저장한다.

B배열도 마찬가지로 진행한다.

 

예시

A배열의 누적합
1 4 5 7
  3 4 6
    1 3
      2
이것들을 다 Map 에 저장

 

B배열을 키값(b배열 누적합)으로 순회하면서 T-(b배열의 누적합)이 A누적합이 저장된 해시 맵에 있는지 확인후

개수를 곱해서 구한다.

 

 

47퍼에서 틀렸었는데 개수는 Integer 범위를 넘어설 수 있기때문이다. 

따라서 Long 타입으로 변경해주었다.

---

🔅 문제 풀이

import java.io.*;
import java.util.*;

public class Main {
    static int T;
    static Map<Integer, Long> aPrefixMap = new HashMap<>();
    static Map<Integer, Long> bPrefixMap = 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));
        T = Integer.parseInt(br.readLine());

        // A배열 초기화
        int n = Integer.parseInt(br.readLine());
        int[] A = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }

        // B배열 초기화
        int m = Integer.parseInt(br.readLine());
        int[] B = new int[m];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) {
            B[i] = Integer.parseInt(st.nextToken());
        }

        // 누적합 Map 생성
        addPrefixSumToMap(n, A, true);
        addPrefixSumToMap(m, B, false);

        long answer = 0;
        // B의 누적합 순회
        for (int prefix : bPrefixMap.keySet()) {
            int findPrefix = T - prefix; // A의 누적합에 findPrefix가 있는지 확인

			// 있다면 B의 누적합의 개수 * A의 누적합의 개수
            answer += bPrefixMap.get(prefix) * aPrefixMap.getOrDefault(findPrefix, 0L);
        }

        System.out.println(answer);
    }

    private static void addPrefixSumToMap(int len, int[] arr, boolean isA) {
        for (int i = 0; i < len; i++) {
            int sum = 0;

            for (int j = i; j < len; j++) {
                sum += arr[j];
                if (isA) {
                    aPrefixMap.put(sum, aPrefixMap.getOrDefault(sum, 0L) + 1L);
                } else {
                    bPrefixMap.put(sum, bPrefixMap.getOrDefault(sum, 0L) + 1L);
                }
            }
        }
    }

}

 

 

 

❗ 오답노트 / 필요한 지식

1.  최악의 경우 즉, 최대 개수일때, 답의 자료형을 뭘사용할지 생각하고 사용하자.