섹션 3. Two points, Sliding window[효율성 : O(n^2)-->O(n)]

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

2. 공통원소구하기( two points algorithm )

3. 최대 매출( Sliding window )

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

5.1 연속된 자연수의 합 ( two pointers )

5.2 연속된 자연수의 합 ( 수학 )

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

 

---

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

 

 

import java.util.*;
public class Main {
    public ArrayList<Integer> solution(int n, int m, int[] a, int[] b){
        ArrayList<Integer> answer=new ArrayList<>();
        int p1=0, p2=0;
        while(p1<n && p2<m) {
            if (a[p1] < b[p2])
                answer.add(a[p1++]); // add 후 p1 증가
            else
                answer.add(b[p2++]);
        }
        while(p1<n) answer.add(a[p1++]);
        while(p2<m) answer.add(b[p2++]);
        return answer;
    }
    public static void main(String[] args){
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        int[] a=new int[n];
        for(int i=0; i<n; i++){
            a[i]=kb.nextInt();
        }
        int m=kb.nextInt();
        int[] b=new int[m];
        for(int i=0; i<m; i++){
            b[i]=kb.nextInt();
        }
        for(int x : T.solution(n,m,a,b)) System.out.print(x+" ");
    }
}

 

 

 

2. 공통원소구하기( two points algorithm )

 

 

 

import java.util.*;
public class Main {
    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){ // two point 알고리즘
            if(a[p1]==b[p2]){
                answer.add(a[p1++]);
                p2++;
            }
            else if(a[p1]<b[p2]) p1++; // 작은쪽 증가
            else p2++;
        }
        return answer;
    }
    public static void main(String[] args){
       Main T=new Main();
       Scanner kb=new Scanner(System.in);
       int n=kb.nextInt();
       int[] a=new int[n];
       for(int i=0; i<n; i++){
           a[i]=kb.nextInt();
       }
       int m=kb.nextInt();
       int[] b=new int[m];
       for(int i=0; i<m; i++){
           b[i]=kb.nextInt();
       }
       for(int x : T.solution(n,m,a,b)) System.out.print(x+" ");
    }
}

 

 

 

3. 최대 매출( Sliding window )

 

 

import java.util.*;
public class Main {
    public int solution(int n, int k, int[] arr){
        int answer=0;
        int sum=0;
        for(int i=0; i<k; i++) sum+=arr[i];
        answer=sum;
        for(int i=k; i<n; i++){
            sum+=(arr[i]-arr[i-k]); // sliding window
            answer=Math.max(answer,sum);
        }
        return answer;
    }
    public static void main(String[] args){
        Main T = new Main();
        Scanner kb=new Scanner(System.in);
        int n=kb.nextInt();
        int k=kb.nextInt();
        int [] arr=new int[n]; // 매출 array
        for(int i=0; i<n; i++){
            arr[i]=kb.nextInt();
        }
        System.out.print(T.solution(n,k,arr));
    }
}

 

 

 

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

 

 

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

 

 

 

5.1 연속된 자연수의 합 ( two pointers )

 

 

import java.util.*;
public class Main {
    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; // 1부터 m까지 순서대로 array
        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;
    }
    public static void main(String[] args){
        Main T = new Main();
        Scanner kb=new Scanner(System.in);
        int n=kb.nextInt();
        System.out.print(T.solution(n));
    }
}

 

 

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

 

 

import java.util.*;
public class Main {
    public int solution(int n, int k, int[] arr){
        int answer=0, cnt=0, lt=0;
       for(int rt=0; rt<n; rt++){
           if(arr[rt]==0)
               cnt++;
           while(cnt>k){
               if(arr[lt]==0) cnt--;
               lt++;
           }
           answer=Math.max(answer,rt-lt+1);
       }
        return answer;
    }
    public static void main(String[] args){
        Main T = new Main();
        Scanner kb=new Scanner(System.in);
        int n=kb.nextInt();
        int k=kb.nextInt();
        int[] arr=new int[n];
        for(int i=0; i<n; i++){
            arr[i]=kb.nextInt();
        }
        System.out.print(T.solution(n,k,arr));
    }
}