350. Intersection of Two Arrays II

두 개의 정수 배열에서 중복된 원소들의 목록을 찾는 문제입니다. 이 문제에서는 중복된 원소를 모두 포함해야 합니다. 즉, 중복된 원소가 여러 번 나타날 수 있으며, 그만큼 결과 목록에도 여러 번 나타나야 합니다.

예를 들어, 두 배열 nums1 = [1, 2, 2, 1]과 nums2 = [2, 2]가 주어진 경우, 이 두 배열의 중복된 원소는 [2, 2]입니다.

이 문제를 해결하기 위한 일반적인 접근 방법은 다음과 같습니다:

하나의 배열을 Dictionary 또는 HashMap에 저장합니다. 이때, 배열의 각 원소를 키로 사용하고, 해당 원소의 빈도(나타난 횟수)를 값으로 저장합니다.

다른 배열을 순회하면서, 각 원소가 Dictionary에 이미 존재하면 빈도를 줄이고 결과 목록에 추가합니다. 빈도가 0이 되면 해당 원소를 제거합니다.

결과 목록을 반환합니다.

 

public int[] Intersect(int[] nums1, int[] nums2) {
    Dictionary<int, int> dic = new Dictionary<int, int>();
    List<int> result = new List<int>();

    // nums1 배열의 모든 원소를 Dictionary에 저장
    foreach (int num in nums1) {
        if (dic.ContainsKey(num)) {
            dic[num]++;
        } else {
            dic[num] = 1;
        }
    }

    // nums2 배열을 순회하며 중복된 원소 찾기
    foreach (int num in nums2) {
        if (dic.ContainsKey(num) && dic[num] > 0) {
            result.Add(num);
            dic[num]--;
        }
    }

    // List를 배열로 변환하여 반환
    return result.ToArray();
}

이 코드는 중복된 원소를 찾기 위해 Dictionary를 사용하고, 중복을 허용하는 경우에도 모든 중복된 원소를 결과 배열에 추가합니다.