JAVA 코딩문제 (두 배열의 교집합)

문제: 두 배열의 교집합

두 개의 정수 배열이 주어졌을 때, 두 배열의 교집합을 구하는 프로그램을 작성하세요. 교집합 배열은 중복된 요소 없이 각 요소가 한 번만 나타나도록 해야 합니다. 교집합 배열의 요소는 오름차순으로 정렬되어 있어야 합니다.

예제

1. 입력: nums1 = [1, 2, 2, 1], nums2 = [2, 2] 출력: [2]
2. 입력: nums1 = [4, 9, 5], nums2 = [9, 4, 9, 8, 4] 출력: [4, 9]

코드

 

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class ArrayIntersection {
    public static int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> intersectionSet = new HashSet<>();
        
        for (int num : nums1) {
            set1.add(num);
        }
        
        for (int num : nums2) {
            if (set1.contains(num)) {
                intersectionSet.add(num);
            }
        }
        
        int[] result = new int[intersectionSet.size()];
        int i = 0;
        for (int num : intersectionSet) {
            result[i++] = num;
        }
        
        Arrays.sort(result);
        return result;
    }
    
    public static void main(String[] args) {
        int[] nums1 = {4, 9, 5};
        int[] nums2 = {9, 4, 9, 8, 4};
        
        int[] result = intersection(nums1, nums2);
        System.out.println(Arrays.toString(result)); // [4, 9]
    }
}

 

해설

1. 문제 정의:
   • 두 개의 정수 배열이 주어졌을 때, 중복 없이 두 배열의 교집합을 찾아 오름차순으로 정렬하여 반환합니다.
2. 해결 방법:
   • 두 배열의 교집합을 찾기 위해 HashSet을 사용합니다. HashSet은 중복된 요소를 허용하지 않으며, 상수 시간 복잡도 내에서 요소를 찾을 수 있습니다.
3. 구현 단계:
   • 첫 번째 배열의 모든 요소를 set1이라는 HashSet에 추가합니다.
   • 두 번째 배열을 순회하면서 set1에 포함된 요소를 intersectionSet에 추가합니다. 이렇게 하면 교집합이 intersectionSet에 저장됩니다.
   • intersectionSet의 요소를 배열로 변환한 후, 오름차순으로 정렬합니다.
   • 정렬된 배열을 반환합니다.
4. 코드 설명:
   • Set<Integer> set1 = new HashSet<>();와 Set<Integer> intersectionSet = new HashSet<>();를 사용하여 중복을 제거하면서 교집합을 구합니다.
   • 첫 번째 for 루프에서 set1에 첫 번째 배열의 모든 요소를 추가합니다.
   • 두 번째 for 루프에서 두 번째 배열의 각 요소가 set1에 있는지 확인하여, 있을 경우 intersectionSet에 추가합니다.
   • 교집합 요소를 배열로 변환한 후, Arrays.sort(result);를 사용하여 오름차순으로 정렬합니다.
   • 최종 결과 배열을 반환합니다.
5. 시간 복잡도:
   • 이 알고리즘의 시간 복잡도는 O(n+m+klog⁡k)O(n + m + k \log k)O(n+m+klogk)입니다. 여기서 nnn과 mmm은 두 배열의 길이이고, kkk는 교집합의 크기입니다.
   • 첫 번째 배열의 모든 요소를 set1에 추가하는 데 O(n)O(n)O(n) 시간이 걸립니다.
   • 두 번째 배열을 순회하면서 교집합을 찾는 데 O(m)O(m)O(m) 시간이 걸립니다.
   • 교집합을 배열로 변환하고 정렬하는 데 O(klog⁡k)O(k \log k)O(klogk) 시간이 걸립니다.

이 코딩 테스트 문제는 집합(Set)과 배열(Array)의 기본적인 사용법을 이해하고, 중복 요소를 제거하며 교집합을 찾는 방법을 익히는 데 도움이 됩니다.