[알고리즘] 03.Two pointers, Sliding window[효율성 : O(n^2)–>O(n)] / 2. 공통원소 구하기

공통원소 구하기

설명

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

입력

첫 번째 줄에 집합 A의 크기 N(1<=N<=30,000)이 주어집니다.
두 번째 줄에 N개의 원소가 주어집니다. 원소가 중복되어 주어지지 않습니다.
세 번째 줄에 집합 B의 크기 M(1<=M<=30,000)이 주어집니다.
네 번째 줄에 M개의 원소가 주어집니다. 원소가 중복되어 주어지지 않습니다.
각 집합의 원소는 1,000,000,000이하의 자연수입니다.

출력

두 집합의 공통원소를 오름차순 정렬하여 출력합니다.

예시 입력 1

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

예시 출력 1

2 3 5

코드

import java.sql.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Main T = new Main();
		Scanner sc = new Scanner(System.in);

		int a = sc.nextInt();
		int[] arrA = new int[a];
		for(int i = 0; i<a; i++) {
			arrA[i] = sc.nextInt();
		}

		int b = sc.nextInt();
		int[] arrB = new int[b];
		for(int i = 0; i<b; i++) {
			arrB[i] = sc.nextInt();
		}

		for(int x : T.solution(a, arrA, b, arrB)) {
			System.out.print(x + " ");
		}
	}

	public ArrayList<Integer> solution(int a, int[] arrA, int b, int[] arrB) {
		ArrayList<Integer> answer = new ArrayList<Integer>();

		Arrays.sort(arrA);
		Arrays.sort(arrB);

		int p1=0, p2=0;
		while(p1<a && p2<b) {
			if(arrA[p1] == arrB[p2]) {
				answer.add(arrA[p1]);
				p1++;
				p2++;
			}else if(arrA[p1] < arrB[p2]) {
				p1++;
			}else {
				p2++;
			}
		}

		return answer;
	}
}