공통 원소 구하기

22 Apr 2023 in Algorithm on Java, Coding, Test

문제

설명

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

해결방법

• 정렬된 상태의 배열이라면, 비교하는 쪽의 포인터가 가리키는 값이 기준 포인터가 가리키는 값보다 크다면, 바로 기준 포인터를 1증가 시키고 진행해도 된다.
• 비교를 할 때는 정렬을 해놓고 하면 좋을 듯?
• Arrays.sort() 함수 이용.

코드

import java.util.*;

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;
        // 2개의 포인터가 각 배열을 순회한다.
        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 T = new Main.Main();
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = kb.nextInt();
        }
        int m = kb.nextInt();
        int[] b = new int[m];
        for (int i = 0; i < m; i++) {
            b[i] = kb.nextInt();
        }
        for (int x : T.solution(n, m, a, b)) System.out.print(x + " ");
    }
}