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)
백준 2143번 : 두 배열의 합 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이..
lotuslee.tistory.com