Open WonYong-Jang opened 5 years ago
2143 두 배열의 합
1) 투 포인터 2) 이분검색
각 배열당 모든 부 배열을(부분집합) 만드는 시간 복잡도는 n^2인데 n 크기가 최대 1000이므로 가능
시나리오
1. 각 배열의 모든 부 배열들을 구하여 subA, subB에 넣는다
2. subA, subB를 오름차순 정렬
3. subA를 왼쪽(L)부터, subB를 오른쪽(R)부터 탐색
4. subA[L] + subB[R] 을 sum이라고 봤을 때
- sum < T 라면 sum의 크기를 더 키워야 하므로 L++
- sum > T 라면 sum 의 크기를 작게해야 하므로 R--
- sum == T 라면 각 배열의 subA[L], subB[R] 과 같은 수의 갯수를 세고 구한 수를 곱한 것을 정답에 더해줌 . 그리고 다음 수를 탐색해야 하므로 L++, R-- 해줌
- 4번을 L과 R이 각 배열의 인덱스 값을 넘어가기 전까지 반복
Arrays.sort(A, 1, index);
Arrays.sort(B, 1, index);
left = 1; right = index-1;
N = index -1;
int sum = 0, temp =0;
int cntA=0, cntB =0;
while(left <= N && right >= 1)
{
sum = A[left] + B[right];
if(sum == 0 ) // 목표값 달성했을 경우 같은 수가 있는지 while문으로 한번 더 체크
{
cntA=0; cntB =0;
temp = A[left];
while(left <= N && temp == A[left]) {
left++;
cntA++;
}
temp = B[right];
while(right >= 1 && temp == B[right]) {
right--;
cntB++;
}
result += (long)cntA*cntB; // 가능한 경우의 수
}
else if( sum > 0) { // 목표값인 0보다 합이 클경우 right 포인터를 줄여서 숫자를 낮춤
temp = B[right];
while(right >= 1 && temp == B[right]) right--;
}
else if( sum < 0) { // 목표값인 0 보다 합이 작을경우 left 포인터를 키워서 숫자를 높힘
temp = A[left];
while(left <= N && temp == A[left]) left++;
}
}
각 배열당 모둔 부 배열을 만들고 오름차순한다. 각각 이분검색을 통해서 T를 만족하는 갯수를 세어줌
만족하는 숫자를 모두 세어줌 == upper_bound(0, arr.size(), diff) - lower_bound(0, arr.size(), diff)
https://www.acmicpc.net/problem/2003 // 투 포인터
https://www.acmicpc.net/problem/11003 ( 데크 사용!) // 슬라이딩 윈도우
슬라이딩 윈도우 (데크 이용)
ex) 11003 예시