공통 원소 구하기

문제

나의풀이

import java.util.*;

class Main {
	public ArrayList<Integer> solution(int n,int m, int[] a,int[] b) {
			ArrayList<Integer> answer = new ArrayList<>();
			int p1 =0, p2 =0;
			Arrays.sort(a);
			Arrays.sort(b);
			while(p1 < n && p2 < m) {
				if(a[p1] < b[p2]) p1++;
				else if(a[p1] > b[p2]) p2++;
				else {answer.add(a[p1]); p1++; 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 + " ");
	}
	
}

풀이방법

예제의 배열 a,b를 sorting 하면
a = [1,2,3,5,9] b = [2,3,5,7,8] 이다.
p1,p2를 0으로 세팅해두고, 만약 두 배열중 작은값이 발견된 배열은
포인터가 1 증가해야한다.
왜냐하면, 큰값이 발견된 배열에는 더이상 발견된 작은값보다 작은값이 없지만,
작은값이 발견된 배열에는 현재 비교되고있는 큰값보다 작은값이 있을수 있기때문이다.

예)
p1=p2=0
1 2 3 5 9
2 3 5 7 8 이라면
a[p1] = 1 vs b[p2] = 2 이다.
이때, p1의 값을 1증가시켜서 다음값이 또 b[p2]의 값보다 큰지 작은지 같은지 판별해야한다.
즉, 현재 선택된 최고값보다 더 높은 값이 있는지 찾기.

그리고 같은값이 발견된다면?
answer에 둘 중 아무값을 넣고
두 배열의 포인터 모두 증가시켜서 다음값들과 비교해야한다.

핵심키워드

작은 값이 발견된쪽의 pointer를 1 증가시키는 이유를 이해하자!