[문제풀이] 03-02. 공통 원소 구하기

인프런, 자바(Java) 알고리즘 문제풀이

Two pointers, Sliding window - 0302. 공통 원소 구하기

🗒️ 문제

🎈 나의 풀이

	private static String solution(int n, int m, int[] arr1, int[] arr2) {
        String answer = "";
        int a = 0, b = 0;

        Arrays.sort((arr1));
        Arrays.sort((arr2));

        while(a < arr1.length && b < arr2.length) {
            if(arr1[a] == arr2[b]) {
                answer += arr1[a] + " ";
                a++;
                b++;
            } else if(arr1[a] > arr2[b]) {
                b++;
            } else a++;
        }

        return answer;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr1 = new int[n];

        for(int i=0; i<n; i++) {
            arr1[i] = sc.nextInt();
        }

        int m = sc.nextInt();
        int[] arr2 = new int[m];

        for(int i=0; i<m; i++) {
            arr2[i] = sc.nextInt();
        }

        System.out.println(solution(n, m, arr1, arr2));
    }

🖍️ 강의 풀이

    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){
		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+" ");
	}

💬 짚어가기

해당 문제는 두 배열 합치기 문제와 거의 동일하다. 입력 받은 두 int 배열을 Arrays.sort()를 통해 정렬하고,
이후 two pointers 알고리즘을 통해 배열을 순회하며 각 요소를 비교하면 된다.