LeetCode 350(Intersection of Two Arrays 2, java)

0. 문제

https://leetcode.com/problems/intersection-of-two-arrays-ii/

Intersection of Two Arrays II - LeetCode

 

1. 문제 설명

- 문제에서 2개의 배열(num1, num2)이 주어진다.

- 두 배열의 원소를 비교하여 양쪽 배열에서 중첩되는 원소를 찾아, 배열의 형태로 반환하는 것이 문제의 핵심이다.

- 다만, 한번 중복된 원소로 걸러진 원소는 다시 사용할 수 없다.

 

2. 문제 해설

- 첫째로, 중첩되는 원소가 몇 개인지 알 수 없다. 그러므로 ArrayList를 사용하여 중첩된 원소를 저장한다.

- 그러나 문제에서 주어지는 메서드의 반환형이 int형 배열이다.

- 그러므로 이 문제 해결하기 위해서는 ArrayList를 int형 배열로 변환하는 방법을 알아야 한다.

 

- 둘째로, 중첩된 원소를 거르는 방법과 한번 걸러진 원소를 다시 비교대상으로 사용하지 않는 것이 중요하다.

- 이를 위해, HashMap을 사용한다.

 

- for문을 사용하여 num1 배열의 원소를 우선 HashMap에 삽입한다.

- 이때 key는 원소가 되고 value는 1씩 증가한다. 

 

- for문을 사용하여 num2 배열의 원소를 순차적으로 탐색한다.

- 이때 num2의 원소가 HashMap에 key로 존재하며, 1 이상의 value를 가지는 경우를 찾는다.

- 위의 조건에 해당하는 key를 찾아 value를 1씩 감소시키며, 해당 원소를 ArrayList에 저장한다.

- 이와 같은 방법을 사용하는 이유는 한번 중첩 원소로 사용된 원소를 다시 사용하지 않기 위함이다.

 

- for문이 종료되면 List 배열을 primitive 배열로 변환하여 반환한다.

 

3. 정답 코드

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        HashMap<Integer, Integer> map = new HashMap<>();
        List<Integer> result = new ArrayList<>();
        
        for(int num : nums1) {
            if(map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
            } else {
                map.put(num, 1);            
            }
        }
        
        for(int num : nums2) {
            if(map.containsKey(num) && map.get(num) >= 1) {
                result.add(num);
                map.put(num, map.get(num) - 1);
            }
        }
        return result.stream().mapToInt(e -> e).toArray();
    }
}