Chapter 03. Two pointers, Sliding window

1. 두 배열 합치기 (two pointers algorithm)

<hide/>
import java.util.*;
public class Main {
  public static void main(String[] args){
   	Main T = new Main();
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    int [] A = new int[n];
	for(int i = 0 ;i < n; ++i){
      A[i] = in.nextInt();
    }
    int m = in.nextInt();
    int [] B = new int[m];
    for(int i= 0; i < m; ++i){
    	B[i] = in.nextInt();
    }
    T.solution(A, B);
    return ;
  }
  
  public void solution (int[] A, int [] B){
  
  int a = A.length;
  int b = B.length;
  int [] answer = new int[a + b];
  
  for(int i = 0; i < a + b; ++i){
  	if(i < a){
 	   answer[i] = A[i];   
    }else{
       answer[i] = B[i-a];
    }
  }  
	Arrays.sort(answer);
    
    for(int i = 0; i < a + b; ++i){
    	System.out.print(answer[i] + " ");
    }
  }
}

  Note)

  - 포인터는 오름차순 정렬

 

 

2. 공통원소 구하기

<hide/>
import java.util.*;
public class Main {
  public static void main(String[] args){
   	Main T = new Main();
    Scanner in=new Scanner(System.in);
    
    int  n = in.nextInt();
    int[] a = new int[n];
    for(int i = 0; i < n; ++i){
    	a[i] = in.nextInt();
    }
    
    int  m = in.nextInt();
    int[] b = new int[m];
    for(int i = 0; i < m; ++i){
    	b[i] = in.nextInt();
    }
    for(int x : T.solution(n, m, a, b)){
    	System.out.print(x + " ");
    }
  }
  
  public ArrayList<Integer> solution(int n, int m, int[] a, int[] b ){
  	ArrayList<Integer> answer = new ArrayList<>();
    Arrays.sort(a);			// 오름차순 정렬
    Arrays.sort(b);
    int p1 = 0, p2 = 0;
    while(p1 < n && p2 < m){		// index는 모두 n또는 m보다 작아야된다.
    	if(a[p1] == b[p2]){
	    	answer.add(a[p1++]);
      		p2++;        
        }else if(a[p1] < b[p2]) p1++;	// 작은 쪽의 포인터를 증가시킨다.
      	 else p2++;
    }
  	return answer;
  }
}

  Note)

  - 교집합 구하기

  - 포인터 p1, p2

  - 포인터는 오름차순 정렬을 시켜야한다.

 

 

3. 최대 매출 (Sliding Window) - Sliding Window

<hide/>
import java.util.*;
public class Main {
  public static void main(String[] args){
    Main T = new Main();
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
	int [] arr = new int[n];
    int k = in.nextInt();
    for(int i = 0 ; i < n; ++i){
    	arr[i] = in.nextInt();
    }
    System.out.println(T.solution(n, k, arr));
    return ;
  }
  
  public int solution(int n, int k, int[] arr){
    int max = 0 ;
    int sum = 0; 
    for(int i = 0 ; i <k ; ++i) sum += arr[i];	// 배열 맨 앞의 k개 만큼의 합을 먼저 구한다.
    max = sum;
    
      for(int i = k; i < n; ++i ){
		 sum += (arr[i] - arr[i-k]);			// Sliding Window (누적시킨다.)
     	 max = Math.max(max, sum);				// 각 실행마다 최댓값을 가려낸다.
      }
    return max;
  }
}

  Note) 

  - 슬라이딩 윈도우로 작성하지 않으면 시간이 초과된다.

  - 따라서, sum += arr[i] - arr[i-k] .. 라고  작성한다.

 

 

4. 연속 부분 수열 (복합적 문제)

<hide/>
import java.util.*;
public class Main {
  public static void main(String[] args){
    Main T= new Main();
    Scanner in=new Scanner(System.in);
    int n = in.nextInt();
   	int [] arr = new int[n];
    int m = in.nextInt();
    for(int i = 0; i < n; ++i){
    	arr[i] = in.nextInt();
    }
    System.out.println(T.solution(n, m, arr));
    return ;
  }
  
  public int solution(int n,  int m, int [] arr){
  
  	int answer = 0;
   	int sum = 0, lt = 0;
    for(int rt = 0; rt < n ; ++rt ){
      sum += arr[rt];
      if(sum == m) answer++;
   	  while(sum >= m){
      	sum -= arr[lt++];
      	if(sum == m) answer++;
      }
    }
  	return answer;
  }
}

 

  Note)

  - N의 최댓값이 10만이면 O(n^2)으로는 부족하다.

  - 포인터 lt, rt를 이용한다.

  - sum이 m보다 작으면 rt를 1씩 증가시킨다.

  - sum이 m보다 커지면 lt가 가리키는 곳의 값을 빼고 lt는 1 증가시킨다.

    -> sum = sum - arr[lt--]

 

 

5. 연속된 자연수의 합  (Two points) 

<hide/>
import java.util.Scanner;
public class Main {
  public static void main(String[] args){
    Main T = new Main();
    Scanner in=new Scanner(System.in);
    int n = in.nextInt();
    System.out.println(T.solution(n));
    return ;
  }
  
  public int solution(int n){
  	int answer = 0, sum = 0, lt = 0;
    int m = n / 2 + 1;
    int [] arr = new int[m];
    for(int i = 0; i < m; ++i) arr[i] = i + 1;
    for(int rt = 0 ; rt < m ; ++rt){
      	sum += arr[rt];
        if(sum == n) answer++;
        while(sum >= n){
        	sum -= arr[lt++];
        	if(sum == n) answer++;
        }
    }
  	return answer;
  }
}

  Note)

  - two point 알고리즘

  - lt, rt를 포인터로 사용한다.

  - sum이 n보다 크거나 같은 경우는 lt번째 값을 빼고 ( sum -= arr[lt]) lt의 값을 증가시켜서 오른쪽으로 이동시킨다.

 

 

 

5. 연속된 자연수의 합  (수학)

<hide/>
import java.util.*;
public class Main {
  public static void main(String[] args){
    Main T= new Main();
    Scanner in=new Scanner(System.in);
    int n = in.nextInt();
    System.out.println(T.solution(n));
    return ;
  }
  
  public int solution(int n){	// 예) n = 15
  
  	int answer = 0, cnt = 1;
    n--;			// n = 14
    
    while(n > 0){	
    	cnt++;		// cnt : 2 -> 3 -> 4 -> 5
     	n -= cnt;	// n = 12 -> 9 -> 5 -> 0
      	if(n % cnt == 0) answer++; 
      
      //(두 개를 더해서 12 가능, 6 + 1 / 6 + 2 ) 
      //(세 개를 더해서 9 가능, 3 + 1 / 3 + 2 / 3 + 3 ) 
      //(다섯 개를 더해서 0가능, 0 + 1 / 0 + 2 / 0 + 3 / 0 + 4 / 0 + 5 )
    }
    
  	return answer;
  }
}

  Note)

  - 조합과 관련된 수학 성질을 이용해서 풀 수도 있다. 

  - cnt는 연속되는 자연수의 개수를 의미한다.

 

 

6. 최대 길이 연속 부분수열 (복합적 문제)

<hide/>
import java.util.*;
public class Main {
  public static void main(String[] args){
    Main T = new Main();
    Scanner in=new Scanner(System.in);
    int n = in.nextInt();
    int k = in.nextInt();
    int [] arr = new int[n];
    for(int i = 0 ;i < n; ++i){
    	arr[i] = in.nextInt();
    } 
    System.out.println(T.solution(n, k, arr));
    return ;
  }
  
  public int solution(int n, int k, int[] arr){		// k : 0을 1로 바꿀 수 있는 횟수
  
    	int answer = 0,  cnt = 0, lt = 0;
    	for(int rt = 0; rt < n ; ++rt){
        	if(arr[rt] == 0)	cnt++;			// arr[rt]를 1로 바꾼다.
          	while(cnt > k ){					// 바꾼 횟수가 가능한 횟수보다 커지는 경우
            	if(arr[lt] == 0) cnt--;			// arr[lt]가 0이면 건너 뛰기 위해 
             	lt++;							// lt를 증가시키고 , cnt는 마이너스시킨다.
            }
          	answer = Math.max(answer, rt - lt + 1);		//연속되는 항의 개수          
        }
   	return answer;
  }
}