<3.2> 공통원소구하기

문제
: 2개의 집합이 배열 입력으로 주어지면 , 두 집합에서 공통원소만을 오름차순으로 출력하는 프로그램을 작성하시오.
(단 입력의 순서는 배열1의 크기 -> 배열1 원소 -> 배열2크기 -> 배열2원소)
(이때 배열1과 배열2의 크기 N,M은 1이상 30000이하의 자연수이다.)
(또한 배열형태로 주어지는 집합의 원소는 1,000,000,000이하의 자연수 이다.)

이 문제의 요구사항은 주어진 그대로 ,
두 배열에서 공통 element값을 추출하여 - 오름차순으로 출력하는 것 이다.

그리고 이에 대한 요구사항으로 아래의 해결 로직을 생각할 수 있었다.

[해결 로직]

• 이전의 3.1문제에서는 입력으로 주어지는 두 배열이 오름차순 정렬되어있었을 경우 -> two pointers algorithm을 써서 오름차순을 유지하면서 한 배열로 합칠 수 있었다.
• 그렇게 할 수 있었던 이유는, 먼저 오름차순으로 정렬된 각 배열에 대해 - two pointers algorithm을 쓰면 - 각 배열의 최솟값에 순차적으로 접근할 수 있었기 때문이다.
• 두 배열간에 (두 집합간에) 공통원소를 구할 때에도 - two pointers algorithm을 써서 각 배열의 최솟값에 순차적으로 접근할 수 있다면 - 공통원소를 쉽게 찾아낼 수 있을 것이라고 생각하였다.

• 예를들어 배열1의 pointer1이 가리키는 최솟값이 1이고 , 배열2의 pointer2가 가리키는 최솟값이 2라면 -> 어쨌든 배열2의 모든 값은 1보단 크다는 의미이므로 -> 1은 공통원소가 될 수 없으니 pointer1을 다음 위치로 옮겨 배열1의 다음 값이 공통원소가 되는지 살펴봐야 한다.

• 반대로 배열1의 pointer1이 가리키는 최솟값이 3이고, 배열2의 pointer2가 가리키는 최솟값이 2라면 -> 배열1의 모든 값은 2보다는 크다는 의미이므로 -> 2는 공통원소가 될 수 없으니 pointer2를 다음 위치로 옮겨 배열 2의 다음 값이 공통 원소가 되는지 살펴봐야 한다.

• 이런식으로 pointer1과 pointer2가 가리키는 배열1과 배열2의 최솟값을 비교하면서 -> 더 작은 쪽의 pointer를 하나씩 옮겨 그 다음 최솟값을 순차적으로 탐색하다보면
  (1) 두 pointer가 가리키는 각 배열의 최솟값이 같지 않다면 그 값은 어차피 최솟값이 될 수 없는 값이니 pointer를 이동시켜 다음 값을 봐야 하고
  (2) 두 pointer가 가리키는 각 배열의 최솟값이 같다면 - 그 값이 곧 두 배열간에 공통 원소가 됨을 알 수 있다.

위와 같은 two pointers algotirhm을 이용한 해결로직을 기반으로 코드를 구현하여 이 문제를 해결할 수 있었다.

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

public class Main {

    public static int[] solution(int[] arr1, int size1, int[] arr2, int size2){
        //1. 일단 두 배열을 오름차순 정렬
        Arrays.sort(arr1);

        Arrays.sort(arr2);



        //2. 이후 Two Pointers 알고리즘을 사용하여 - 오름차순으로 정렬된 두 배열의 element를 순차적으로 "최솟값 부터 비교하면서"
        // 두 값이 같지 않으면 -> 더 작은쪽 배열의 pointer를 이동시키고  / 두 값이 같으면 - 공통원소이므로 결과 리스트에 넣고 - 양쪽 배열의 pointer를 모두 이동시킨다
        // 그러다가 둘 중 한 pointer가 size에 도달하면 - 한쪽 배열 탐색이 끝났다는 뜻 이므로 -> 더이상 공통원소가 없다는 뜻! -> so 곧바로 결과 리스트를 반환 하면 됨!
        int p1 = 0, p2 = 0, p3 = 0;
        int[] arr3 = new int[size1+size2];

        while(p1<size1 && p2<size2){
            if(arr1[p1] < arr2[p2]){
                p1++;
            } else if(arr1[p1] > arr2[p2]){
                p2++;
            } else{
                arr3[p3++] = arr1[p1];
                p1++;
                p2++;
            }

        }

        return arr3;


    }

    public static void main(String[] args) {
        //0. Scanner 준비
        Scanner sc = new Scanner(System.in);

        //1. 두 배열 입력
        int size1 = sc.nextInt();
        int[] arr1 = new int[size1];
        for(int i=0; i<size1; i++){
            arr1[i] = sc.nextInt();
        }

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

        //2. 두 배열과 각 배열의 크기를 인자로 넘기면서 solution()을 호출하여 결과 배열을 List 형태로 반환
        int[] resultArr = solution(arr1, size1, arr2, size2);

        //3, 결과 List의 element를 순차 출력 함
        for(int i=0; resultArr[i]!=0; i++){
            System.out.print(resultArr[i] + " ");
        }
    }
}

단 공통원소를 담는 결과 배열을 순수 배열이 아닌 List를 사용하였을 경우 시간초과 가 되었는데
-> 이는 List에는 객체값만 담을 수 있기에
-> Integer값과 int값 사이에 auto boxing과 auto unboxing이 빈번하게 일어나야만 하고
-> 이로 인해 시간 초과가 난 것 같았다.

따라서 공통원소를 담는 공간을 순수한 배열로 수정 하여 시간 초과 없이 문제를 해결할 수 있었다.