2143 두 배열의 합

 

 

1. 풀이

 

다른 블로그를 참고해서 풀었다.

 

누적 합과 두 포인터를 이용한다.

 

예제를 가지고 설명하겠다.

 

5
4
1 3 1 2
3
1 3 2

 

 

 

 

1)  누적합

 

 

A 배열에 1 3 1 2 를 입력하고,

B 배열에 1 3 2를 입력한다.

 

그 후 sumA 리스트에 

A 배열의 누적 합을 넣어준다.

 

A[0] 

A[0] + A[1]

A[0] + A[1] + A[2]

A[0] + A[1] + A[2] + A[3]

 

A[1]

A[1] + A[2]

A[1] + A[2] + A[3]

 

A[2]

A[2] + A[3]

 

A[3]

 

이런 식으로 누적 합을 sumA리스트에 넣어준다.

그 후 오름차순 정렬해준다.

 

B 배열의 누적 합도 마찬가지로 만들어준다.

 

=> 

 

sumA : 1 1 2 3 3 4 4 5 6 7

sumB : 1 2 3 4 5 6

 

2) 두 포인터

여기서 사용되는 두 포인터는

sumA 리스트의 인덱스, sumB 리스트의 인덱스이다.

 

sumA 리스트의 인덱스 : a

=> 0부터 시작

=> 점점 증가시킴

 

 

sumB 리스트의 인덱스 : b

=> sumB 리스트의 마지막부터 시작 (즉 b는 5부터 시작)

=> 점점 감소시킴

 

1. 

sumA의 a번째 값 + sumB의 b번째 값 = 5

=> 문제에서 찾고자 하는 경우이다.

 

2.

sumA 의 a번째 값 + sumB 의 b 번째 값 < 5 

=> a를 증가시켜서 5와 일치하는 경우가 있는지 확인한다.

 

a를 증가시키면 리스트 sumA에서 더 큰 값을 얻을 수 있기 때문이다.

즉 A배열 누적 합 중 더 큰 부분을 얻을 수 있다.

 

3.

sumA의 a번째 값 + sumB의 b번째 값 > 5

=> b를 감소시켜서 5와 일치하는 경우가 있는지 확인한다.

 

이런식으로 문제를 해결하면 된다.

 

2. 최종 코드

 

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

public class Main {

	static long result;
	static ArrayList<Integer> sumA; 
	static ArrayList<Integer> sumB;
	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 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());
		}
		
		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());
		}
		
		sumA = new ArrayList<>();
		sumB = new ArrayList<>();
		
		
		for(int i=0; i<n; i++) {
			
			int number = 0;
			
			for(int j=i; j<n; j++) {
			
				number+=A[j];
				sumA.add(number);
			}
		}
		

		for(int i=0; i<m; i++) {
		
			int number = 0;
			
			for(int j=i; j<m; j++) {
				
				number+=B[j];
				sumB.add(number);
			}
		}
		
		Collections.sort(sumA);
		Collections.sort(sumB);
		
		
		result = 0;
		solve();
		
	
		System.out.println(result);
	}
	
	public static void solve() {
		
		int a = 0;
		int b = sumB.size()-1;
	
		while(a < sumA.size() && b>=0) {
					
			long resultA = 0;
			long resultB = 0;
			
			int sum = sumA.get(a) + sumB.get(b);
			
			if(sum == T) {
				
				int valueA = sumA.get(a);
				int valueB = sumB.get(b);
				
				while (a <sumA.size() && valueA==sumA.get(a)) {
					resultA++;
					a++;
				}

				while (b>=0 && valueB == sumB.get(b)) {
					resultB++;
					b--;
				}
			
				result+= resultA*resultB;
				
			}else if (sum <T) {
					a++;
					
			}else if (sum >T) {
					b--;
			}
		}
	}
}

 

참고 블로그 : 

https://lotuslee.tistory.com/31

[백준 2143번] 두 배열의 합 (java)