[Java] 공통 원소 구하기 | 인프런 | 투 포인터 알고리즘

문제

 

풀이

두 개의 배열이 주어지고 인덱스를 활용해서 풀 수 있는 문제이므로 투포인터 알고리즘을 사용하는 문제입니다.

투 포인터 알고리즘을 사용하라면 두 배열이 주어지고 정렬이 되어있어야 합니다. 이번 문제는 정렬이 되어있지 않아서 정렬을 해야 합니다.

 

- 두 인덱스가 유효한 상태에서 반복을 계속합니다

- 만약 해당 인덱스의 두 원소가 값이 같으면 리스트에 넣고 두 인덱스 값을 1 증가합니다.

- 만약 A배열의 원소가 더 크면 두 번째 배열의 인덱스를 1 증가시킵니다.

- 만약 B배열의 원소가 더 크면 첫 번째 배열의 인덱스를 1 증가시킵니다.

 

이미 정렬을 한 상태이므로 리스트에는 오름차순으로 저장되어 있습니다. 따라서 반환만 해주면 됩니다.

 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
/*
* - A 배열을 정렬합니다.
* - B 배열을 정렬합니다.
* - p1<n && p2<m일 상태를 유지하는 동안 반복합니다.
* - A[p1] == B[p2]이면 해당 값을 리스트에 넣습니다.
* - A[p1]>B[p2]이면 p2를 1 증가합니다.
* - A[p1]<B[p2]이면 p1을 1 증가합니다.
*
*
* */
public class Main {
    public static ArrayList<Integer> solution(int n, int[] A, int m, int[] B) {
        int p1 = 0;
        int p2 = 0;
        ArrayList<Integer> list = new ArrayList<>();
        Arrays.sort(A);
        Arrays.sort(B);

        while(p1<n && p2<m) {
            if (A[p1] == B[p2]) {
                list.add(A[p1]);
                p1++;
                p2++;
            }
            else if(A[p1] > B[p2]) p2++;
            else p1++;
        }
        return list;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] A = new int[n];
        for (int i=0; i<n; i++) {
            A[i] = in.nextInt();
        }
        int m = in.nextInt();
        int[] B = new int[m];
        for (int i=0; i<m; i++) {
            B[i] = in.nextInt();
        }
        for (int x : solution(n,A,m,B)) {
            System.out.print(x + " ");
        }
    }
}