[코테 3_2] 공통원소 구하기

✔ 내 답 -> 정답인데 타임 초과

https://kjhoon0330.tistory.com/entry/Java-List-%EC%A0%95%EB%A0%AC%EC%97%90-%EB%8C%80%ED%95%98%EC%97%AC
list를 정렬하는 방법

import java.util.*;

public class P3_2{
  public static List<Integer> solution(int[] arr1, int[] arr2){
 
    List<Integer> answer = new ArrayList<Integer>();   
 
    for(int i=0;i<arr1.length;i++){
      for(int j=0;j<arr2.length;j++){
          if(arr1[i]==arr2[j]&& !answer.contains(arr1[i])) answer.add(arr1[i]);
        }
   }
  Collections.sort(answer);

   return answer;
  }
  public static void main(String[] args){

    Scanner kb = new Scanner(System.in);

    int a1 = kb.nextInt();
    int[] arr1 = new int[a1];
    for(int i=0;i<a1;i++)  arr1[i]=kb.nextInt();
    
    int a2 = kb.nextInt();
    int[] arr2 = new int[a2];
    for(int j=0;j<a2;j++)  arr2[j]=kb.nextInt();
   
    for(int x : solution(arr1,arr2)) System.out.print(x+" ");   

  }
}

✔️ 강의 조금 듣고 힌트를 얻음 -> 먼저 정렬
정렬할 때 두 가지 방식
1) array 정렬할 때 -> Array.sort()/ Arrays.sort(nums,Collections.reverseOrder());
2) list 정렬할 때 -> Collections.sort() /Collections.sort(list, Collections.reverseOrder());

import java.util.*;

public class Main{
	public static ArrayList<Integer> solution(int[] arr1 , int[] arr2){
		ArrayList<Integer> answer = new ArrayList<>();
		Arrays.sort(arr1);
		Arrays.sort(arr2);
		int op =0, tp=0;
		
	    while(op<arr1.length && tp<arr2.length) {
	    	if(arr1[op]<arr2[tp]) op++;
	    	else if(arr1[op]==arr2[tp]) {
	    		answer.add(arr1[op]);
	    		op++;
	    		tp++;
	    	}
	    	else tp++;
	    }
		
		
		return answer;
			
	}
	
	public static void main(String[] args) {
		Scanner kb = new Scanner(System.in);
		int a1_len = kb.nextInt();
		int[] arr1 = new int[a1_len];
		for(int i=0; i<a1_len;i++) {
			arr1[i]=kb.nextInt();
		}
		int a2_len = kb.nextInt();
		int[] arr2 = new int[a2_len];
		for(int i=0; i<a2_len;i++) {
			arr2[i]=kb.nextInt();
		}
		for(int x : solution(arr1,arr2)) System.out.print(x+" ");
		
	}
	
	
	
}

중요한 것은 먼저 작은 두개의 배열을 정렬한 후에
포인터를 사용해서 앞으로 전진하기

그전의 사용하던 함수들은 arr1.length * arr2.length 번만큼 돌려서 값을 구하기 때문에

위의 방법은 arr1.length + arr2.length번 만큼만 비교해서 교집합을 구함