[Inflearn] 자바 알고리즘 문제풀이 #03-02 2. 공통원소 구하기

문제

설명

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

 

입력 

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

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

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

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

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

 

출력 

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

 

 

 

내 풀이

import java.util.ArrayList;
import java.util.Comparator;
import java.util.Scanner;

public class Main3_2 {
    public ArrayList<Integer> Solution(int n, int m, int[] a, int[] b) {
        ArrayList<Integer> answer = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if(a[i]==b[j]) answer.add(a[i]);
            }
        }
        answer.sort(Comparator.naturalOrder());
        return answer;
    }


    public static void main(String[] args) {
        Main3_2 T = new Main3_2();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        int m = sc.nextInt();
        int[] b = new int[m];
        for (int i = 0; i < m; i++) {
            b[i] = sc.nextInt();
        }
        for (int x : T.Solution(n, m, a, b)) {
            System.out.print(x + " ");
        }
    }
}

Time Limit ㅎㅎㅎㅎ

03-01 문제에서 했던 것 처럼, p1 p2로 나눠서 두 배열에 각각 접근하는 방식을 "two pointers algorithm"라고 한다.

이 문제도 그런 식으로 풀어야 함.. 03-01은 워밍업 이었던 듯

 

https://rookie-programmer.tistory.com/50

[Inflearn] 자바 알고리즘 문제풀이 #03-01 1. 두 배열 합치기

 

 

 

선생님 풀이

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main3_2 {
    public ArrayList<Integer> Solution(int n, int m, int[] a, int[] b) {
        ArrayList<Integer> answer = new ArrayList<>();
        Arrays.sort(a);
        Arrays.sort(b);
        int p1=0, p2=0;
        while(p1<n && p2<m) {
            if(a[p1]==b[p2]) {
                answer.add(a[p1++]);
                p2++;
            }
            else if (a[p1]<b[p2]) p1++;
            else p2++;
        }
        return answer;
    }


    public static void main(String[] args) {
        Main3_2 T = new Main3_2();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        int m = sc.nextInt();
        int[] b = new int[m];
        for (int i = 0; i < m; i++) {
            b[i] = sc.nextInt();
        }
        for (int x : T.Solution(n, m, a, b)) {
            System.out.print(x + " ");
        }
    }
}

강의에서는 9, 10번째 줄을 Array.sort(a) Array.sort(b)라고 쓰셨는데 버전이 다른건지 나한테는 Arrays.sort()가 맞았다.

이렇게 풀어내니 쉽고 실행 속도도 그냥 씹어 먹네.. 힝'^' 이렇게 못 풀어서 아쉬워

 

 

 

결과

 

 

 

알게된 점

1. 배열 정렬 (Array sort), ArrayList 정렬(ArrayList sort)

https://rookie-programmer.tistory.com/52

[JAVA] Array sort, ArrayList sort (배열 정렬, ArrayList sort 정렬)