두 배열의 공통 원소 찾기 및 투 포인터 알고리즘

문제. A, B 두 개의 배열이 주어지면 두 집합의 공통 원소를 추출하여 오름차순으로 출력하는 프로그램을 작성하세요.  

 

입력 예시

5
1 3 9 5 2
5
3 2 5 7 8

 

답 :  2 3 5 

 

나의 답변

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

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

 

 

정정 답변

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

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

 

 

투 포인터 알고리즘 사용
두 개의 포인터를 사용하여 배열이나 리스트를 한 번에 효율적으로 탐색하거나 정렬하는 알고리즘

•  첫 번째 답변은 이중반복문으로 시간복잡도가 O(N^2)
•  정정 답변은 투 포인터 알고리즘을 사용하므로 O(N) >>>> 효율적