LeetCode 350. Intersection of Two Arrays II

nang_nang·2022년 10월 3일

PS

목록 보기

3/18

📝 LeetCode 350 풀이

💡문제 정의

LeetCode 350 << 링크

nums1과 nums2가 주어졌을 때, 교집합 요소들을 뽑아 배열을 만들어야 한다. 만약 nums1과 nums2에서 9가 각각 2번, 3번 등장했다면, 교집합 배열에는 [9, 9, ...]처럼 9가 2번 포함되어야 한다.
배열의 결과에서 요소들의 순서는 중요하지 않다. [4, 9]나 [9, 4] 모두 동일한 것으로 취급한다.

두 배열의 크기 및 각 배열 요소의 크기는 위와 같다.

💡풀이

1-1) C

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* intersect(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize){
    int size = (nums1Size < nums2Size) ? nums1Size : nums2Size;
    int* arr = (int *)malloc(sizeof(int) * size);
    int checkNums1[1001] = {0,}, checkNums2[1001] = {0,};
    int index = 0;
    
    for (int i = 0;i < nums1Size;i++) {
        checkNums1[nums1[i]]++;
    }

    for (int i = 0;i < nums2Size;i++) {
        checkNums2[nums2[i]]++;
    }

    for (int i = 0;i < 1001;i++) {
        if (checkNums1[i] && checkNums2[i]) { // if both are larger than 0
            int cnt = (checkNums1[i] < checkNums2[i]) ? checkNums1[i] : checkNums2[i];
            for (int j = 0;j < cnt;j++)
                arr[index++] = i;
        }
    }

    *returnSize = index;

    return arr;
}

우선 malloc을 시행할 때, nums1과 nums2 중 크기가 더 작은 배열의 크기만큼 메모리를 할당하도록 했다. 물론 배열의 크기가 1000 이하로 제한되어 있어서 그냥 1000만큼 할당해도 될 것 같다.

그리고 nums1과 nums2 배열 요소들의 등장 횟수를 저장할 checkNums1, checkNums2 배열을 선언했다. 두 배열의 크기는 1001이고, 배열 요소의 값은 모두 0으로 초기화했다.

nums1[i]가 한 번 나타나면 checkNums1[nums[i]]의 값을 1씩 증가시키는 형태! 이후 checkNums1과 checkNums2 배열을 돌면서, 두 배열 모두의 i번째 값이 0보다 크다면 cnt를 둘 중 더 작은 값으로 초기화. 최종적으로 return할 arr 배열에 i를 cnt번 추가한다.

그런데 마지막 for문에서 1001번 loop를 도는 것이 마음에 들지 않았다.

1-2) C

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* intersect(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize){
    int size = (nums1Size < nums2Size) ? nums1Size : nums2Size;
    int* arr = (int *)malloc(sizeof(int) * size);
    int checkNums1[1001] = {0,};
    int index = 0;
    
    for (int i = 0;i < nums1Size;i++) {
        checkNums1[nums1[i]]++;
    }

    for (int i = 0;i < nums2Size;i++) {
        if (checkNums1[nums2[i]]) { // larger than 0
            arr[index++] = nums2[i];
            checkNums1[nums2[i]]--;
        }
    }

    *returnSize = index;

    return arr;
}

위와 같이 코드를 조금 개선!

2-1) Python

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        cnt = dict()
        result = list()
        for i in range(len(nums1)): 
            if nums1[i] in cnt.keys():
                cnt[nums1[i]] += 1
            else:
                cnt[nums1[i]] = 1

        for i in range(len(nums2)):
            if nums2[i] in cnt.keys() and cnt[nums2[i]]:
                result.append(nums2[i])
                cnt[nums2[i]] -= 1

        return result

cnt라는 딕셔너리의 값을 for문을 통해 직접 채웠는데 아래와 같이 Counter 클래스를 사용하면 더 간편!

2-2) Python

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        cnt = Counter(nums1)
        result = list()

        for n in nums2:
            if cnt[n]:
                result.append(n)
                cnt[n] -= 1

        return result