[알고리즘] P2143. 두 배열의 합

package day02.P2143;
// 두 배열의 합 풀다가 못풀었음

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
	static int[] A, B, SubA, SubB;
	static int num1, num2, T;
	
	public static void main(String[] args) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		num1 = Integer.parseInt(st.nextToken());
		A = new int[num1];
		
		for(int i = 1; i<=num1;i++) {
			A[i] = Integer.parseInt(st.nextToken());
		}
		num2 = Integer.parseInt(st.nextToken());
		B = new int[num2];
		
		for(int i = 1; i<=num2;i++) {
			B[i] = Integer.parseInt(st.nextToken());
		}
		
		SubA = new int[num1*num1];
		SubB = new int[num2*num2];
		calSub(A[], SubA[]);
		
		
	}
	
	
	
	
	static int[] calSub(int[] value, int[] Sub) {
		int index = 0;
		for(int i = 0; i<= value.length; i++) {
			int sum = 0;
			Sub[index++] = value[i];
			sum += value[i];
			for(int j = i+1; j<=value.length; j++) {
				Sub[index++] = sum + value[j];
				sum += value[j];
			}
		}
		
		
		return Sub;
	}
	
}

 

계속 풀려고 하는데 실패중..

 

 

 

package day02.P2143;
// 두 배열의 합

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

import java.util.StringTokenizer;

public class Main {
	static long[] inputA, inputB;
	static int M,N;
	static long T;                               
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		T = Long.parseLong(br.readLine());
		N = Integer.parseInt(br.readLine());
		
		inputA = new long[N];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			inputA[i] = Long.parseLong(st.nextToken());
		}
		
		M = Integer.parseInt(br.readLine());
		inputB= new long[M];
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i<M; i++) {
			inputB[i] = Long.parseLong(st.nextToken());
		}
		
		List<Long> subA = new ArrayList<>();
		List<Long> subB = new ArrayList<>();
		
		for(int i = 0; i<N; i++) {
			long sum = 0;
			for(int j = i; j<N; j++) {
				sum += inputA[j];
				subA.add(sum);
			}
		}
		
		for(int i = 0; i<M; i++) {
			long sum = 0;
			for(int j = i; j<M; j++) {
				sum += inputB[j];
				subB.add(sum);
			}
		}
		
		Collections.sort(subA);
		Collections.sort(subB, Comparator.reverseOrder());
		
		long result = 0;
		int ptA = 0;
		int ptB = 0;
		
		while(true) {
			long currentA = subA.get(ptA);
			long target = T - currentA;
			
			if(subB.get(ptB) > target) {
				ptB++;
			}else if (subB.get(ptB) < target) {
				ptA++;
			}else { // 동률찾기 while문도 가능한다 만약에 전체가 다 동률이 같으면 n번 검사해야함
			// lower bound upper bound 개념 보고 도입하면 더 빠르게 구할 수 있음
				long countA = 0;
				long countB = 0;
				while(ptA < subA.size() && subA.get(ptA) == currentA) {
					// 같은 동률이니까
					countA++;
					ptA++;
				} 	
				while(ptB < subB.size() && subB.get(ptB) == target) {
					countB++;
					ptB++;
				} 
				result += countA + countB;
			}
			
			if(ptA == subA.size() || ptB == subB.size()) { // 탈출조건
				break;
			}
			
			
			
		}
		System.out.println(result);
		
		
	}
	
	
	
	

	
}

 

 

근데 왜 안되냐고.... 아ㅏ아ㅏㅏㅏ

 

이 문제가 두 배열 A,B의 부 배열의 합이 T가 되는 모든 부 배열의 쌍의 갯수를 찾는 것인데

 

 내 코드에서는 부 배열의 합의 조합이 중복되어서 발생하고 있어서 오류가 발생함.

 

-> 솔직히 나는 저 코드를 보고 어떻게 중복된 게 포함이 되서 오류가 나는건지 알지 못했음

 

너무 어렵다

 

 

package day25.P2143_두배열의합;
// 두 배열의 합

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

import java.util.StringTokenizer;

public class Main {
	static long[] inputA, inputB;
	static int M,N;
	static long T;                               
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		T = Long.parseLong(br.readLine());
		N = Integer.parseInt(br.readLine());
		
		inputA = new long[N];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			inputA[i] = Long.parseLong(st.nextToken());
		}
		
		M = Integer.parseInt(br.readLine());
		inputB= new long[M];
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i<M; i++) {
			inputB[i] = Long.parseLong(st.nextToken());
		}
		
		List<Long> subA = new ArrayList<>();
		List<Long> subB = new ArrayList<>();
		
		for(int i = 0; i<N; i++) {
			long sum = 0;
			for(int j = i; j<N; j++) {
				sum += inputA[j];
				subA.add(sum);
			}
		}
		
		for(int i = 0; i<M; i++) {
			long sum = 0;
			for(int j = i; j<M; j++) {
				sum += inputB[j];
				subB.add(sum);
			}
		}
		// 부 배열 정렬
		Collections.sort(subA);
		Collections.sort(subB);
		// 그냥 둘다 똑같이 정렬해놓고 탐색할때만 B를 뒤에서부터 찾음
		long result = 0;
		int ptA = 0;
		int ptB = subB.size() - 1; // 역순으로 탐색하기 위해 인덱스 설정
		
		while(ptA < subA.size() && ptB >= 0) {
		    long sum = subA.get(ptA) + subB.get(ptB);
		    if(sum == T) {
		        long countA = 1, countB = 1;
		        // A 배열에서 같은 부 배열 합의 개수 세기
		        while(ptA + 1 < subA.size() && subA.get(ptA).equals(subA.get(ptA + 1))) {
		            ptA++;
		            countA++;
		        }
		        // B 배열에서 같은 부 배열 합의 개수 세기
		        while(ptB - 1 >= 0 && subB.get(ptB).equals(subB.get(ptB - 1))) {
		            ptB--;
		            countB++;
		        }
		        result += countA * countB;
		        ptA++; // 다음 부 배열 합으로 이동
		        ptB--; // 다음 부 배열 합으로 이동
		    } else if(sum < T) {
		        ptA++;
		    } else {
		        ptB--;
		    }
		}
		System.out.println(result);
		
		
	}
	
	
	
	

	
}

 

-> 이렇게 고치니까 맞음

 

나중에 한 달 정도 뒤에 다시 풀어보자 너무 어렵네