Two Pointers_교집합 구하기

✅ 두 집합의 교집합을 오름차순으로 구하세요

class Main {

    public ArrayList<Integer> solution(int n, int[] intArrA, int m, int[] intArrB){
        ArrayList<Integer> answer= new ArrayList<>();
        Arrays.sort(intArrA);
        Arrays.sort(intArrB);
        int pi=0;
        int pj=0;
        while(pi<n && pj<m){
            if(intArrA[pi] < intArrB[pj]){
                pi++;
            }
            else if(intArrA[pi] == intArrB[pj]){
                answer.add(intArrA[pi++]);
                pj++;
            }
            else pj++;
        }
    return answer;
}
    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc= new Scanner(System.in);
        int n = sc.nextInt();
        int[] intArrA = new int[n];
        for(int i=0; i<n; i++){
            intArrA[i] = sc.nextInt();
        }
        int m = sc.nextInt();
        int[] intArrB = new int[m];
        for(int j=0; j<m; j++){
            intArrB[j] = sc.nextInt();
        }
        for(int x: T.solution(n, intArrA, m, intArrB)){
            System.out.print(x+ " ");
        }
    }
}

//⭐️input:
// 5
// 1 3 9 5 2 배열 A
// 5
// 3 2 5 7 8 배열 B
//⭐️output:
//2 3 5

1. 먼저 두 배열을 오름차순으로 정리한다. Arrays.sort(intArrA);
   
2. intArrA[pi] < intArrB[pj] 일 때는 intArrB배열을 더 볼 필요가 없다.
   왜? 현재 두 배열이 오름차순으로 정리되어 있으므로, intArrA[pi]이 더 작은데 어떻게 같을 수 있겠어. 그러니까 pi++
   
3. intArrA[pi] == intArrB[pj]일 때는 answer에 추가하고, pi, pj모두 하나씩 증가
   
4. intArrA[pi] > intArrB[pj]일 때는 뒤에있는 intArrB[pj]중에 intArrA[pi]랑 일치하는 숫자가 있을 수도 있으므로 pj++
   

🔵 ThingsILearned

💡 two pointer알고리즘은 꼭 오름차순을 구현한 후 시작한다.

✔️ 모든 수를 비교할 필요 없는 경우들도 있다. 비교할 필요가 없는 경우들은 아얘 비교하지 말하버리자.

이 경우 intArrA[pi] < intArrB[pj] 일 때는 비교하지 않아버려도 괜찮기 때문에 더 이상 비교하지 말고 그냥 비교를 끝내버린다.

🔴 이렇게 풀면 다 run time error time limit exceed

class Main {

    public ArrayList<Integer> solution(int n, int[] intArrA, int m, int[] intArrB){
        ArrayList<Integer> answer= new ArrayList<>();
        Arrays.sort(intArrA);
        Arrays.sort(intArrB);
        int pi=0;
        while(pi<n){
            int pj=0;
            while(pj<m) {
                if (intArrA[pi] == intArrB[pj]) answer.add(intArrA[pi++]);
                else pj++;
            }
            pi++;
        }

        // 🔴 또는 이렇게 풀어도 time limit exceed
//    for(int i=0; i<n; i++){
//        for(int j=0; j<m; j++){
//            if(intArrA[i] == intArrB[j]) answer.add(intArrA[i]);
//        }
//    }
    return answer;
}
    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc= new Scanner(System.in);
        int n = sc.nextInt();
        int[] intArrA = new int[n];
        for(int i=0; i<n; i++){
            intArrA[i] = sc.nextInt();
        }
        int m = sc.nextInt();
        int[] intArrB = new int[m];
        for(int j=0; j<m; j++){
            intArrB[j] = sc.nextInt();
        }
        for(int x: T.solution(n, intArrA, m, intArrB)){
            System.out.print(x+ " ");
        }
    }
}