25. 공통원소 구하기

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

 

내가 푼 풀이과정

- Stream 사용해서 풀어봄

package org.example;

import java.util.*;
import java.util.function.Predicate;

public class Main {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        List<Integer> a = new ArrayList<>();
        for(int i=0; i<n; i++){
            a.add(in.nextInt());
        }
        int m = in.nextInt();
        List<Integer> b = new ArrayList<>();
        for(int i=0; i<m; i++){
            b.add(in.nextInt());
        }

        // 오름차순 정렬
        List<Integer> matchList = a.stream()
                        .filter(o -> b.stream()
                        .anyMatch(Predicate.isEqual(o)))
                        .sorted(Comparator.naturalOrder()).toList();

        for(int x : matchList){
            System.out.print(x + " ");
        }
    }
}

 

다른 풀이과정

• 두 배열에 각각 오름차순으로 우선 넣어둔다.
• 같은 값일때 answer 배열에 insert 하고 두 포인터 모두 증가시킴 
• 만약 아닐때는 작은쪽 배열 포인터 증가시킴 => 오름차순이기 때문에 작은쪽을 증가시켜준다.
• 아무쪽이나 하나만 끝나면 이제 공통원소가 없으니 비교 끝내면 됨

package org.example;

import java.util.*;

public class Main {
    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){
        Main main = new Main();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] a = new int[n];
        for(int i=0; i<n; i++){
            a[i] = in.nextInt();
        }
        int m = in.nextInt();
        int[] b = new int[m];
        for(int i=0; i<m; i++){
            b[i] = in.nextInt();
        }
        for(int x : main.solution(n,m,a,b)) System.out.print(x + " ");
    }
}