[인프런] 공통원소 구하기

난이도

• Easy

문제 설명

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
출력: 2,3,5

접근 방법

• 순회와 set을 이용해 동일한 값만 결과값에 담아 출력

시간 및 공간 복잡도

• 시간 복잡도 : O(NlogN)
  • 입력 받은 원소들을 HashSet에 저장: O(N) + O(M)
  • HashSet의 contains 연산: O(1)
  • 결과 리스트 정렬: O(KlogK) (K는 공통 원소의 개수로, 최대 min(N,M))
  • 따라서 전체 시간 복잡도는 정렬이 지배적이므로 O(NlogN)
• 공간 복잡도: O(N + M)
  • 첫 번째 집합을 저장하는 HashSet: O(N)
  • 두 번째 집합을 저장하는 HashSet: O(M)
  • 결과를 저장하는 ArrayList: O(min(N,M))
  • 따라서 전체 공간 복잡도는 O(N + M)

코드 구현

public class App {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Set<Integer> set1 = new HashSet<>();
        for (int i = 0; i < n; i++) {
            set1.add(sc.nextInt());
        }

        int k = sc.nextInt();

        List<Integer> answer = new ArrayList<>();

        Set<Integer> set2 = new HashSet<>();
        for (int i = 0; i < k; i++) {
            set2.add(sc.nextInt());
        }
        for (int num : set2) {
            if (set1.contains(num)) {
                answer.add(num);
            }
        }

        Collections.sort(answer);
        for (int num1 : answer) {
            System.out.print(num1 + " ");
        }
    }
}