[JAVA11/알고리즘]3-2 공통원소 구하기

문제

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

 

입력

첫 번째 줄에 집합 A의 크기 N(1<=N<=30,000)이 주어집니다.

두 번째 줄에 N개의 원소가 주어집니다. 원소가 중복되어 주어지지 않습니다.

세 번째 줄에 집합 B의 크기 M(1<=M<=30,000)이 주어집니다.

네 번째 줄에 M개의 원소가 주어집니다. 원소가 중복되어 주어지지 않습니다.

각 집합의 원소는 1,000,000,000이하의 자연수입니다.

 

출력 

두 집합의 공통원소를 오름차순 정렬하여 출력합니다.

 

예시 입력 1 

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

예시 출력 1

 

2 3 5

 

해결

문제를 보자마자 간단하게 생각하였었다.

두 집합에 공통원소를 ArrayList에 집어넣고 collections.sort를 이용해 끝내려고 했다.

 

import java.util.*;

public class Main {
    public static ArrayList<Integer> solution(int n, int m, int[] arr1, int[] arr2){
        ArrayList<Integer> answer = new ArrayList<Integer>();
        for(int i=0; i<n;i++){
            for(int j=0; j<m; j++){
                if(arr1[i] == arr2[j]) answer.add(arr1[i]);
            }
        }
        Collections.sort(answer);

        return answer;
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr1 = new int[n];
        for(int i=0;i<n; i++){
            arr1[i] = in.nextInt();
        }
        int m = in.nextInt();
        int[] arr2 = new int[m];
        for(int i=0;i<m; i++){
            arr2[i] = in.nextInt();
        }
        for(int x : solution(n,m,arr1,arr2)){
            System.out.print(x+ " ");
        }

    }
}

생각처럼 쉽게 코드가 짜였다. 그러나, 시간 제한을 훌쩍 뛰어넘어버려 시간초과가 이루어 졌다.

 

collections.sort는 팀 정렬을 사용하는데 이것의 시간복잡도는 nlogn

위에 이중for문을 사용하였으니 내 코드의 시간복잡도는 n^2 +nlogn인데 , nlogn은 무시해도 되니 n^2이다.

크기를 오름차순 정렬하여 출력하여야 되니 collections.sort는 어쩔수 없이 사용해야된다.

시간복잡도를 nlogn으로 줄이면 될 문제 같았다.

 

그래서 Two Pointers 알고리즘을 사용하기로 했다.

두개의 포인터가 일차원 배열 위를 움직이며 서로 비교하는 알고리즘인데 two Pointes 알고리즘의 시간복잡도는 n밖에 되지 않는다. 

 

정수 배열 두개를 먼저 Arrays.sort를 이용해 정렬해주고, 포인터 p1, p2가 그 배열위에서 각각 움직인다.

공통 원소를 골라내야 하니, 두 포인터가 가리키는 값이 같으면 answer라는 ArrayList에 더해주면 되고 같지 않으면, 둘 중 가리키는 값이 더 작은 포인터가 한칸 움직이면 된다.

CODE
 

import java.util.*;

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

    }
}

 

 

결과

위가 Two Pointers 알고리즘,

밑이 이중 반복문을 사용한 것이다.

시간이 확연히 차이난다.