[백준] 두 배열의 합 - 2143 Java

백준의 두 배열의 합 문제를 풀어보았다.(Java)

 

구현에 사용한 알고리즘은 TwoPointer이다.

 

TwoPointer에 대해 생소하여서 기존에 풀었던 기초라고 생각한 문제로 다시 풀어보았다.

 

이번 문제로 개념을 좀 잡은 것 같다.

 

작성한 코드는 아래와 같다.

 

두 배열의 부분합을 계산한 뒤 리스트에 넣고 정렬한다.

정렬한 리스트를 토대로 투 포인터를 사용하여 제시한 합과 동일한 부분합을 계산한다.

 

 

package baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class BOJ2143 {
	
	static List<Integer> listA;
	static List<Integer> listB;
	static int T;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		T = Integer.parseInt(br.readLine());
		
		int numA = Integer.parseInt(br.readLine());
		int[] A = new int[numA];
		String[] arrA = br.readLine().split(" ");
		for(int i = 0; i < numA; i++) {
			A[i] = Integer.parseInt(arrA[i]);
		}
		
		int numB = Integer.parseInt(br.readLine());
		int[] B = new int[numB];
		String[] arrB = br.readLine().split(" ");
		for(int i = 0; i < numB; i++) {
			B[i] = Integer.parseInt(arrB[i]);
		}
		
		listA = new ArrayList<>();
		listB = new ArrayList<>();
		
		for(int i = 0; i < numA; i++) {
			int sum = 0;
			for(int j = i; j < numA; j++) {
				sum += A[j];
				listA.add(sum);
			}
		}
		
		for(int i = 0; i < numB; i++) {
			int sum = 0;
			for(int j = i; j < numB; j++) {
				sum += B[j];
				listB.add(sum);
			}
		}
		
		Collections.sort(listA);
		Collections.sort(listB);
		
		System.out.println(compute());
	}
	
	public static long compute() {
		int pa = 0;
		int pb = listB.size() - 1;
		long count = 0;
		
		while(pa < listA.size() && pb >= 0) {
			long sum = listA.get(pa) + listB.get(pb);
			
			if(sum == T) {
				int a = listA.get(pa);
				int b = listB.get(pb);
				long countA = 0;
				long countB = 0;
				
				while (pa < listA.size() && listA.get(pa) == a) {
					countA++;
					pa++;
				}
				while (pb >= 0 && listB.get(pb) == b) {
					countB++;
					pb--;
				}
				
				count += countA * countB;
			}
			
			else if(sum < T) {
				pa++;
			}
			else if(sum > T){
				pb--;
			}
		}
		
		return count;
		
	}
}