[백준] code.plus(브루트포스 - 기타,JAVA)2143번, 두 배열의 합

문제 링크

2143번: 두 배열의 합

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

브루트 포스란.

모든 경우의 수를 대입시켜서 가장 알맞은 경우의 수를 결과로 출력하는 것입니다.

이 문제에 핵심은

1. 배열에는 부 배열이 존재합니다.

2. 부 배열의 합을 이루려면 연속적이어야 합니다.

3. 2개의 배열에 부 배열에 합이 T가 되는 횟수를 결과로 출력합니다.

 

각 배열에 대한 부 배열의 합의 경우를 누적합을 이용하여 구하였습니다.

 

누적합으로 구한 부 배열의 합들을 더했을 때 T가 나오는 횟수는 두 포인터를 이용하여 구하였습니다.

 

예제입력1

 

A

1

3

1

2

누적합

1	3	1	2
1	4	5	7

누적합을 이용해서 나올 수 있는 부 배열의 합의 경우{1, 1, 2, 3, 3(4-1), 4, 4(5-1), 5, 6(7-1), 7}

 

B

1

3

2

누적합

1	3	2
1	4	6

누적합을 이용해서 나올 수 있는 부 배열의 합의 경우

{1, 2,  3, 4,  5(6-1), 6}

 

※원래는 구하면 정렬되어 있지 않지만 두 포인터를 이용하기 위해서 저는 오름차순으로 정렬을 하였습니다.

 

2개의 부배열의 합을 더해서 T가 나오는 횟수를 구하면 됩니다.

(1, 4), (1, 4), (2, 3), (3, 2), (3, 2), (4, 1), (4, 1) = 7개

 

횟수를 구할 때에는 두 포인터 알고리즘을 이용하여 횟수를 구하였습니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 이용하여 배열에 대한 정보를 저장하였습니다.
• 누적합을 이용해서 모든 경우의 부 배열의 합을 구하는 sumCal함수를 실행하였습니다.
• 두 포인터를 이용하기 위해서 오름차순 정렬을 하였습니다.
• 두 부 배열의 합의 합이 T가 되는 개수를 구하는 compare함수를 실행하였습니다.
• T가 나오는 개수를 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• sumCal함수는 2중 for문과 누적합을 이용해서 모든 경우의 부 배열 합을 ArrayList<>에 저장하였습니다.
• compare함수는 두 포인터 알고리즘을 이용하여 합이 T가 되는 개수를 구하였습니다.

 

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

public class Main{
	static int T, n, m;
	static long[] A,B;	//배열 A, B
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        	//입력값 처리하는 BufferedReader
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        	//결과값 출력하는 BufferedWriter
		StringTokenizer st;
		T = Integer.parseInt(br.readLine());
		n = Integer.parseInt(br.readLine());
		A = new long[n+1];
		st = new StringTokenizer(br.readLine()," ");
        	//A배열 누적합 구하기
		for(int i=1;i<=n;i++)
			A[i] = A[i-1]+Integer.parseInt(st.nextToken());
		
		m = Integer.parseInt(br.readLine());
		B = new long[m+1];
		st = new StringTokenizer(br.readLine()," ");
        	//B배열 누적합 구하기
		for(int i=1;i<=m;i++)
			B[i] = B[i-1] + Integer.parseInt(st.nextToken());
            
		ArrayList<Long> sumA = new ArrayList<>();
		ArrayList<Long> sumB = new ArrayList<>();
		
		sumCal(sumA, A);	//A 부 배열의 합 모든 경우 구하기
		sumCal(sumB, B);	//B 부 배열의 합 모든 경우 구하기
			//부 배열의 합 오름차순 정렬
		Collections.sort(sumA);
		Collections.sort(sumB);
		long result = compare(sumA, sumB);	//합이 T가 되는 경우 구하기
		bw.write(result + "\n");		//T가되는 횟수 BufferedWriter 저장
		bw.flush();		//결과 출력
		bw.close();
		br.close();
	}
    	//두 부 배열의 합이 T가 되는 횟수를 구하는 두 포인터 함수
	static long compare(ArrayList<Long> A, ArrayList<Long> B) {
		long count = 0;
		int aIdx = 0;	//A 부 배열 시작 Index
		int bIdx = B.size()-1;	//B 부 배열 시작 Index
		while(true) {
			if(aIdx>=A.size() || bIdx <0)	//부 배열 범위 벗어날 때
				break;
			long a = A.get(aIdx);
			long b = B.get(bIdx);
			long sum = a+b;
			if(T==sum) {	//합이 T가 되었을 때
				long aCount = 0;
                		//While문으로 반복하는 이유는 동일한 값이 존재할 수 있기 때문입니다.
				while(aIdx<A.size() && A.get(aIdx) == a) {
					aCount++;
					aIdx++;
				}
				long bCount = 0;
				while(bIdx>=0 && B.get(bIdx)==b) {
					bCount++;
					bIdx--;
				}
				count += aCount * bCount;
			}
			if(T>sum)	//합이 T보다 작을 경우 aIndex++
				aIdx++;
			else if(T<sum)	//합이 T보다 클 경우 bIndex--
				bIdx--;
		}
		return count;		//횟수 반환
	}
    	//누적합을 이용하여 부 배열의 합 모든 경우 구하는 함수
	static void sumCal(ArrayList<Long> list, long[] arr) {
		for(int i=arr.length-1;i>0;i--) {
			for(int j=0;j<i;j++) {
				list.add(arr[i] - arr[j]);
			}
		}
	}
}