투 포인터 / 슬라이딩 윈도우

[WonYong-Jang]

https://www.acmicpc.net/problem/2003 // 투 포인터

https://www.acmicpc.net/problem/11003 ( 데크 사용!) // 슬라이딩 윈도우

• 2905 홍준이와 울타리

슬라이딩 윈도우 (데크 이용)

ex) 11003 예시

• 데크의 앞쪽 : 문제에서 주어진 조건을 만족하는 최소값 유지 / 윈도우 범위가 넘어 갈때는 만족하는 범위가 나올때까지
  빼줌
  -데크의 뒤쪽 : 넣을 num 값 보다 같거나 크면 num 보다 작은 값 나올때까지 pollLast

for(int i=1; i<= N; i++)
{
	num = Integer.parseInt(st.nextToken());
	data[i] = num;
			
	Node first = null, last = null;
	while(!que.isEmpty()) // 조건 만족할때 가지 데크 뒤 빼기 ////////빼는 구간 
	{
		last = que.peekLast();
				
		if(last.num >= num) que.pollLast();
		else break;
	}
	que.addLast(new Node(num, i));
			
	int target = 0;
	while(!que.isEmpty()) ///////////////////////////////// 넣는 구간
	{
		first = que.peekFirst();
		last = que.peekLast();
				
		target = first.num;
		if(last.idx - first.idx < X)
		{
			break;
		}
		que.pollFirst();
	}
}

[WonYong-Jang]

관련문제

2143 두 배열의 합

두가지 풀이 가능

1. 투 포인터
2. 이분검색

1. 투 포인터

각 배열당 모든 부 배열을(부분집합) 만드는 시간 복잡도는 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++;
	}
}

(그림)풀이 참고 : https://m.blog.naver.com/PostView.nhn?blogId=withham1&logNo=221053472141&proxyReferer=https%3A%2F%2Fwww.google.com%2F

2. 이분검색

각 배열당 모둔 부 배열을 만들고 오름차순한다. 각각 이분검색을 통해서 T를 만족하는 갯수를 세어줌

만족하는 숫자를 모두 세어줌 == upper_bound(0, arr.size(), diff) - lower_bound(0, arr.size(), diff)

#23 upper_bound / lower_bound 개념 참고

[WonYong-Jang]

관련문제

• leetcode (다시풀기)

689. Maximum Sum of 3 Non-Overlapping Subarrays
690. 3Sum
691. 4Sum => 리스트 중복 제거 하기 !