99클럽 코테 스터디 16일차 TIL + LeetCode 349 (Intersection of Two Arrays, java)

오늘의 학습 키워드

• 이분탐색
• HashSet

 

문제 탐색하기

 

문제 풀이 설계하기

저는 HashSet의 교집합을 구하는 메소드를 활용해서 풀었습니다.

제 풀이 말고도 이분탐색으로 푸는 법이 있어서 2가지 방식으로 풀어보도록 하겠습니다.

 

코드

1. HashSet으로 풀이

import java.util.*;

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        
        Integer[] nums1Boxed = Arrays.stream(nums1).boxed().toArray(Integer[]::new);
        Integer[] nums2Boxed = Arrays.stream(nums2).boxed().toArray(Integer[]::new);
        Set<Integer> nums1Set = new HashSet<Integer>(Arrays.asList(nums1Boxed));
        Set<Integer> nums2Set = new HashSet<Integer>(Arrays.asList(nums2Boxed));

        nums1Set.retainAll(nums2Set);
        int[] result = nums1Set.stream().mapToInt(i -> i).toArray();
        return result;
    }
}

 

• int[] 배열을 Set으로 변환하기 위해서 int 배열을 Integer 배열로 변환해서 Set으로 변환
• Set 의 retainAll 메소드를 통해서 교집합을 구함

 

2. 이분탐색으로 풀이

 

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

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        // nums1을 정렬합니다.
        Arrays.sort(nums1);
        Set<Integer> intersectionSet = new HashSet<>();

        // nums2의 각 원소에 대해 nums1에서 이분 탐색을 수행합니다.
        for (int num : nums2) {
            if (binarySearch(nums1, num)) {
                intersectionSet.add(num);
            }
        }

        // Set을 배열로 변환하여 반환합니다.
        int[] result = new int[intersectionSet.size()];
        int index = 0;
        for (int num : intersectionSet) {
            result[index++] = num;
        }
        return result;
    }

    // 이분 탐색 함수
    private boolean binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2; // 오버플로우 방지
            if (arr[mid] == target) {
                return true;
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }
}

 

 

 

오늘의 회고

HashSet의 메소드를 이용해서 풀었는데 시간이 꽤 오래 걸려서 찾아보니 이분탐색으로 풀이하는 방법도 있었다는 것을 알 수 있었습니다. 다른 방식으로 풀어보면서 내 코드의 문제점을 알 수 있게 되는 시간이었습니다.