[ 백준 ] 2143 두 배열의 합

codesver·2023년 3월 12일
0

Baekjoon

목록 보기
20/72
post-thumbnail

Link | 백준 2143번 문제 : 두 배열의 합

📌 About

이번 문제는 사실 n과 m의 크기가 작기 때문에 brute force로 해결할 수 있다.

📌 Solution

이중 반복문을 통해 모든 범위의 합산값을 계산한다.

int[] arr = new int[LEN];

for (int i = 0; i < arr.length; i++) {
	int sum = 0;
   	for (int j = i; j < arr.length; j++) {
    	sum += arr[j];
        // sum = 부분합
    }
}

이 때 동일한 합산값에 대해서는 개수를 센다.

Map<Integer, Integer> map = new HashMap<>();

for (int s = 0; s < A.length; s++) {
    int sum = 0;
    for (int e = s; e < A.length; e++) AS.merge(sum += A[e], 1, Integer::sum);
}

두 배열 A와 B에 대해서 각각의 map을 만든다.

Map<Integer, Integer> AS = new HashMap<>();
for (int s = 0; s < A.length; s++) {
    int sum = 0;
    for (int e = s; e < A.length; e++) AS.merge(sum += A[e], 1, Integer::sum);
}

Map<Integer, Integer> BS = new HashMap<>();
for (int s = 0; s < B.length; s++) {
    int sum = 0;
    for (int e = s; e < B.length; e++) BS.merge(sum += B[e], 1, Integer::sum);
}

경우의 수는 다음과 같이 구한다. 이 때 경우의 수는 long이 되어야 한다.

long count = AS.entrySet().stream()
        .mapToLong(entry -> (long) BS.getOrDefault(T - entry.getKey(), 0) * entry.getValue())
        .sum();

📌 Code

GitHub Repository

public void solve() throws IOException {
    final int T = Integer.parseInt(reader.readLine());

    int N = Integer.parseInt(reader.readLine());
    int[] A = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

    int M = Integer.parseInt(reader.readLine());
    int[] B = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

    Map<Integer, Integer> AS = new HashMap<>();
    for (int s = 0; s < A.length; s++) {
        int sum = 0;
        for (int e = s; e < A.length; e++) AS.merge(sum += A[e], 1, Integer::sum);
    }

    Map<Integer, Integer> BS = new HashMap<>();
    for (int s = 0; s < B.length; s++) {
        int sum = 0;
        for (int e = s; e < B.length; e++) BS.merge(sum += B[e], 1, Integer::sum);
    }

    result.append(AS.entrySet().stream()
            .mapToLong(entry -> (long) BS.getOrDefault(T - entry.getKey(), 0) * entry.getValue())
            .sum());
}
profile
Hello, Devs!

0개의 댓글