2143번 : 두 배열의 합 [Java]

https://www.acmicpc.net/problem/2143

2143번: 두 배열의 합

해결 방법

투 포인터 알고리즘을 사용한다.

 

전체 코드

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

public class Main {

	static int T;
	static int n, m;
	static int[] A, B;
	static List<Integer> listA = new ArrayList<>();
	static List<Integer> listB = new ArrayList<>();

	public static void main(String[] args) throws Exception {

		BufferedReader input = new BufferedReader(new InputStreamReader(System.in));

		T = Integer.parseInt(input.readLine());

		n = Integer.parseInt(input.readLine());
		A = new int[n];
		StringTokenizer st = new StringTokenizer(input.readLine(), " ");
		for (int i = 0; i < n; i++)
			A[i] = Integer.parseInt(st.nextToken());

		m = Integer.parseInt(input.readLine());
		B = new int[m];
		st = new StringTokenizer(input.readLine(), " ");
		for (int i = 0; i < m; i++)
			B[i] = Integer.parseInt(st.nextToken());

		for (int i = 0; i < n; i++) {
			int sum = 0;
			for (int j = i; j < n; j++) {
				sum += A[j];
				listA.add(sum);
			}
		}
		for (int i = 0; i < m; i++) {
			int sum = 0;
			for (int j = i; j < m; j++) {
				sum += B[j];
				listB.add(sum);
			}
		}

		Collections.sort(listA);
		Collections.sort(listB);

		System.out.println(getCount());

	}

	public static long getCount() {

		int pa = 0;
		int pb = listB.size() - 1; 
		long cnt = 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 aCnt = 0;
				long bCnt = 0;

				while (pa < listA.size() && listA.get(pa) == a) {
					aCnt++;
					pa++;
				}

				while (pb >= 0 && listB.get(pb) == b) {
					bCnt++;
					pb--;
				}

				cnt += aCnt * bCnt;
			}

			else if (sum < T)
				pa++;

			else if (sum > T)
				pb--;
		}

		return cnt;

	}
}