[Java] 3-2 공통원소 구하기

문제

A, B 두 개의 집합이 주어지면 두 집합의 공통 원소를 추출하여 오름차순으로 출력하는 프로그램을 작성하세요.
입력
첫 번째 줄에 집합 A의 크기 N(1<=N<=30,000)이 주어집니다.
두 번째 줄에 N개의 원소가 주어집니다. 원소가 중복되어 주어지지 않습니다.
세 번째 줄에 집합 B의 크기 M(1<=M<=30,000)이 주어집니다.
네 번째 줄에 M개의 원소가 주어집니다. 원소가 중복되어 주어지지 않습니다.
각 집합의 원소는 1,000,000,000이하의 자연수입니다.
출력
두 집합의 공통원소를 오름차순 정렬하여 출력합니다.
예시 입력

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

예시 출력

2 3 5

출처
인프런 - 자바-알고리즘-문제풀이-코테대비

내 풀이

private static List<Integer> getIntersection(int num1, int num2, int[] arr1, int[] arr2) {
    ArrayList<Integer> result = new ArrayList<>();

    for (int i = 0; i < num1; i++) {
        for (int j = 0; j < num2; j++) {
            if (arr1[i] == arr2[j]) {
                result.add(arr1[i]);
                break;
            } else if (arr1[i] < arr2[j]) {
                break;
            }
        }
    }

    result.sort(Integer::compareTo);
    return result;
}

시간제한을 못넘었다

다른 풀이

/* 강의 풀이 */
public static ArrayList<Integer> solution(int num1, int num2,
                                          int[] arr1, int[] arr2) {
    ArrayList<Integer> answer = new ArrayList<>();
    Arrays.sort(arr1);
    Arrays.sort(arr2);
    int index1 = 0, index2 = 0;

    // 어느 한 배열이 끝에 도달하면 비교를 멈춘다
    while(index1 < num1 && index2 < num2) {
        if(arr1[index1] == arr2[index2]) {
            answer.add(arr1[index1]);
            index1++;
            index2++;
        } else if(arr1[index1] < arr2[index2]) {
            index1++;
        } else {
            index2++;
        }
    }

    return answer;
}

정렬한 뒤 비교하여 비교횟수를 줄였다

기억할 점

Arrays.sort(arr)

배열을 오름차순으로 정렬한다