2. 공통 원소 구하기

1. 문제

두 배열의 공통 원소를 추출하여 오름차순으로 출력하는 프로그램을 작성하자.

 

2 - 1. 나의 풀이

투 포인터를 사용하지 않았다.

1. 입력 값을 Set에 저장한다.

2. Set의 교집합 메서드 retainAll()을 사용한다.

3. Collections.sort() 를 사용해 오름차순 정렬한다.

2 - 2. 나의 코드

import java.util.*;

public class twoPoint02 {
    public static ArrayList<Integer> solution(Set a, Set b) {
        a.retainAll(b);
        ArrayList<Integer> answer = new ArrayList<>(a);
        Collections.sort(answer);

        return answer;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Set<Integer> a = new HashSet<>();
        Set<Integer> b = new HashSet<>();
        int n1 = sc.nextInt();
        for (int i = 0; i < n1; i++) {
            a.add(sc.nextInt());
        }

        int n2 = sc.nextInt();
        for (int i = 0; i < n2; i++) {
            b.add(sc.nextInt());
        }

        for (int x : solution(a, b)) {
            System.out.print( x + " ");
        }


    }
}

 

3 - 1. 강의 풀이

투 포인터를 사용해 풀었다.

 

1. 두 배열에 포인터 p1, p2를 초기화한다.

2. a[p1]과 b[p2]를 비교한다.

3. 둘이 같다면 배열의 값을 ArrayList에 추가하고, p1과 p2를 증가한다. (p1과 p2 중 하나만 증가해도 상관없다)

4. 둘이 같지 않다면 둘 중 작은 쪽의 포인터를 증가시킨다.

 

3 - 2. 강의 코드

import java.util.*;

public class towPoint02_solution {
    public static ArrayList<Integer> solution(int[] a, int[] b, int n1, int n2) {
        ArrayList<Integer> answer = new ArrayList<>();
        int p1 = 0, p2 = 0;
        Arrays.sort(a);
        Arrays.sort(b);
        while (p1 < n1 && p2 < n2) {
            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) {
        Scanner sc = new Scanner(System.in);
        int n1 = sc.nextInt();
        int[] a = new int[n1];
        for (int i = 0; i < n1; i++) {
            a[i] = sc.nextInt();
        }

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

        for (int x : solution(a, b, n1, n2)) {
            System.out.print(x + " ");
        }

    }
}

 

4. 얻어갈 점

포인터의 활용 복습해두면 시간 복잡도 상으로 굉장히 유용할 듯!!