Two pointers, Sliding window[효율성 : O(n^2)-->O(n)] - 두 배열 합치기 / 공통원소 구하기

 

 두 배열 합치기

 

two pointer 알고리즘 사용

o(nlogn)이 아닌 o(n) 으로 짜는 것

 

오름차순으로 정렬된 두 배열을 오름차순으로 합쳐 출력
a[p1] < b[p2] 비교하는 것

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++]); // p1의 값이 add 된 후 p1 1 증가
            else answer.add(b[p2++]);
        }
        while(p1<n) answer.add(a[p1++]); // p1이 남아 있으면,
        while(p2<m) answer.add(b[p2++]); // 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+" ");
    }
}

 

 공통 원소 구하기

 

Two pointers 알고리즘
- 순서
 1. 미리 오름차순 정렬을 한다. 
 2. 비교하면서 작은 것을 하나 플러스 한다. a[p1] < b[p1] 이면 a를 플러스
 3. 같으면 동시에 증가

 

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;
        int p2 = 0; // 순서 초기화
        while(p1 < n && p2 < m){
            if(a[p1]==b[p2]){
                answer.add(a[p1]);
                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+" ");
    }
}