[알고리즘] Two pointers, Sliding window(2) : 공통원소 구하기(JAVA)

👕 공통원소 구하기

문제

풀이

🎨 pointer의 사용

• 두 배열 a,b 를 오름차순으로 정렬한다.

배열 a의 pointer를 p1, 배열 b의 pointer를 p2라고 한다.

a[p1], b[p2]의 값을 비교한다

a[p1]<b[p2] 이므로 p1의 값을 1증가 시켜준다.
b배열은 p2의 값을 증가 시켜도 오름차순으로 정렬되었기 때문에 같은 값이 있을 수 없다.

• a[p1] == b[p2] 가 되었으므로, a[p1], b[p2] 중 둘 중 하나를 answer에 저장한다.

• 같은 값이 나올땐 , p1,p2의 값을 동시에 1씩 증가시켜 준다.

a[p1] > b[p2] 일때, 작은 값인 p2의 값을 ++ 해준다.

소스코드

🎨 공통원소 구하기 전체 소스코드

package algolecture;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main26 {
    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){

            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) {
        Main26 T = new Main26();
        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+" ");

    }
}