공통원소 구하기

설명

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 (시간 제한 걸림,,)

import java.util.ArrayList;
import java.util.Scanner;
//공통원소 구하기 Time limit 걸림
public class Main {
    public static ArrayList<Integer> solution(int N, int M, int[] A, int[] B) {
        ArrayList<Integer> tmp = new ArrayList<>();
        ArrayList<Integer> ans = new ArrayList<>();

		//같은 원소만 추출해 tmp에 추가한다.
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (A[i] == B[j]) {
                    tmp.add(A[i]);
                    break;
                }
            }
        }

		//tmp(공통원소) 오름차순
        while (tmp.size() != 0) {
            int min = Integer.MAX_VALUE;

            for (int i = 0; i < tmp.size(); i++) {
                if (tmp.get(i) < min) { //tmp 원소에서 가장 작은 것 min에 저장
                    min = tmp.get(i);
                }
            }
            ans.add(min); //최소값 ans에 저장
            tmp.remove(tmp.indexOf(min)); //방금 뽑은 최솟값 tmp에서 제거
        }

        return ans;
    }

    public static void main(String[] args) {
        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 s : solution(N, M, A, B)) {
            System.out.print(s + " ");
        }
    }
}

 

 

소스 코드 2

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

//공통원소 구하기
public class Main {
    public static ArrayList<Integer> solution(int N, int M, int[] A, int[] B) {
        ArrayList<Integer> ans = new ArrayList<>();
        int pA = 0, pB = 0; //A와 B 인덱스 값으로 사용할 변수
        //A, B 오름차순 정렬
        Arrays.sort(A);
        Arrays.sort(B);
        while (pA < N && pB < M) { //A,B 중 하나가 인덱스 끝을 볼 때 까지 반복
            if (A[pA] < B[pB]) { //A값이 작다면 인덱스 카운트
                pA++;
            } else if (A[pA] > B[pB]) { //B값이 작다면 인덱스 카운트
                pB++;
            } else { //A,B 원소가 같다면 ans에 추가후 A,B 모두 카운트
                ans.add(A[pA]);
                pA++;
                pB++;
            }
        }

        return ans;
    }

    public static void main(String[] args) {
        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 s : solution(N, M, A, B)) {
            System.out.print(s + " ");
        }
    }
}

 

 

Arrays.sort()

 - 배열을 오름차순 해준다

 - A = {1,5,3,4,2} 였을 때 Arrays.sort(A)를 사용하면 A = {1,2,3,4,5}가 된다.