[Algorithm] 공통원소구하기

공통원소 구하기

설명

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

---

해결

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public ArrayList<Integer> solution(int n, int m, int[] a, int[] b) {
        ArrayList<Integer> answer = new ArrayList<>();
        int pos1=0, pos2=0;
        // 배열 정렬
        Arrays.sort(a);
        Arrays.sort(b);

        // 두 배열 중 한 배열의 순회가 끝날때 까지 반복
        while (n>pos1 && m>pos2) {
            if (a[pos1] > b[pos2]) {
                pos2++;
            } else if (b[pos2] > a[pos1]) {
                pos1++;
            // a와 b 배열의 요소가 같은 경우, answer에 넣어야 하는 경우    
            } else {
                answer.add(a[pos1]);
                pos1++;
                pos2++;
            }
        }

        return answer;
    }

    public static void main(String[] args) throws IOException {
        Main T = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int[] array1;
        int[] array2;

        int N = Integer.parseInt(br.readLine());
        array1 = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i=0; st.hasMoreTokens(); i++) {
            array1[i] = Integer.parseInt(st.nextToken());
        }

        int M = Integer.parseInt(br.readLine());
        array2 = new int[M];
        st = new StringTokenizer(br.readLine());
        for (int i=0; st.hasMoreTokens(); i++) {
            array2[i] = Integer.parseInt(st.nextToken());
        }

        for (int i : T.solution(N, M, array1, array2)) {
            System.out.print(i + " ");
        }
    }
}

• 두 배열의 공통 원소를 추출하는 문제였다.
• 공통 원소를 구하기 위해 두 배열을 오름차순 정렬시키고, 각 배열의 포인터 변수들을 활용해 while문으로 순회하며 공통원소를 추출했다.