설명

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

코드

public class SameTwoArray {
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        int input1 = in.nextInt();
        int[] arr1 = new int[input1];
        for(int i=0; i<input1; i++){
            arr1[i] = in.nextInt();
        }
        int input2 = in.nextInt();
        int[] arr2 = new int[input2];
        for(int i=0; i<input2; i++){
            arr2[i] = in.nextInt();
        }

        ArrayList<Integer> solution = solution(arr1, arr2);
        for (int i : solution) {
            System.out.print(i+" ");
        }
    }

    public static ArrayList<Integer> solution(int[] arr1, int[]arr2){
        ArrayList<Integer> answer = new ArrayList<>();
        Arrays.sort(arr1);
        Arrays.sort(arr2);
        int p1 = 0;
        int p2 = 0;
        while(p1<arr1.length && p2<arr2.length){
            int su1 = arr1[p1];
            int su2 = arr2[p2];
            //같은지 검사
            if(su1==su2){
                answer.add(su1);
                p1++;
                p2++;
            }else{//아니라면 누가 큰지 검사
                if(su1>su2)
                    p2++;
                else
                    p1++;
            }
        }
        return answer;
    }
}

문제에서 중요한 점은 입력되는 원소들이 정렬되어 있지 않은 배열이기 때문에 두 배열을 먼저 정렬해주어야 한다는 점이다.

배열을 정렬한 뒤 두 포인터를 반복문을 통해 배열을 비교하며 증가시키면 되는데 저번 문제와 다르게 마지막 while문이 없는 이유는 두 배열 중 하나의 배열이라도 끝까지 돌았다면 이미 모두 검사를 끝냈기 때문이다.

해당 알고리즘은 손으로 코딩할 수 있을 정도로 간단한 개념이기 때문에 손코딩 문제로 나올수도 있다고 한다. 꼭 자기가 직접 문제를 풀어보자!

두 배열을 비교하라고 할땐 항상 two pointers 기억하자!