Intuition

두 배열을 각각 살펴보고 공통되는 것을 결과배열에 담아주면 되겠다고 생각했다.

Approach

두 배열을 순회하며 등장할 수 있는 숫자 0~1000을 count하는 배열 n1, n2를 만들었다.
이때, 원소 i의 개수는 n[i]에 저장된다.
res는 결과값을 담을 배열, cnt는 공통 element 개수를 세는 변수다.

	int *res=(int*)malloc(sizeof(int)*MIN(nums1Size,nums2Size));
    int n1[1001], n2[1001], cnt=0;
    for (int i=0;i<1001;i++){
        n1[i]=0;
        n2[i]=0;
    }

    for (int i=0;i<nums1Size;i++) n1[nums1[i]]++;
    for (int i=0;i<nums2Size;i++) n2[nums2[i]]++;

n1과 n2에서 원소 i의 개수 n[i]가 더 적은 쪽을 택하면 공통되는 원소 i가 몇개인지 알 수 있다. 그 개수만큼 res배열에 넣어준다.

    for (int i=0;i<nums1Size;i++) n1[nums1[i]]++;
    for (int i=0;i<nums2Size;i++) n2[nums2[i]]++;

    for (int i=0;i<1001;i++){
        for (int j=0;j<MIN(n1[i],n2[i]);j++){
            res[cnt++]=i;
        }
    }

    *returnSize=cnt;
    return res;

Solution

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

#define MIN(a,b) ((a)<(b)?(a):(b))

int* intersect(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize){
    int *res=(int*)malloc(sizeof(int)*MIN(nums1Size,nums2Size));
    int n1[1001], n2[1001], cnt=0;
    for (int i=0;i<1001;i++){
        n1[i]=0;
        n2[i]=0;
    }

    for (int i=0;i<nums1Size;i++) n1[nums1[i]]++;
    for (int i=0;i<nums2Size;i++) n2[nums2[i]]++;

    for (int i=0;i<1001;i++){
        for (int j=0;j<MIN(n1[i],n2[i]);j++){
            res[cnt++]=i;
        }
    }

    *returnSize=cnt;
    return res;
}
}

Complexity

Time Complexity

두 배열의 길이를 각각 N,M이라 하면 한 번씩 순회하므로 $O(N+M)$, 공통된 원소의 길이는 N+M을 넘지 않으므로 $O(N+M)$이라 할 수 있다.

Space Complexity

두 배열 N,M 그리고 공통 배열의 길이를 담을 크기만큼이 필요하다. $O(N+M)$

교수님 풀이

위 풀이에서 n1과 n2에 대해 모두 한번씩 순회한 후 공통원소를 비교했다면, 이 풀이는 n1에 대해서만 원소의 개수를 세고 n2는 그때그때 n1에 해당 원소가 있는지를 체크하는 방식으로 공통원소여부를 판단한다.

n1의 원소를 count하는 과정까지는 동일하다.

int *res=(int*)malloc(sizeof(int)*MIN(nums1Size,nums2Size));
    int n1[1001], cnt=0;

    for (int i=0;i<1001;i++) n1[i]=0;

    for (int i=0;i<nums1Size;i++) n1[nums1[i]]++;

n2를 순회하며 n2의 원소가 n1에도 있는지를 체크한다. 만약 존재한다면 원소개수를 하나 차감시키고 결과배열에 해당 원소를 넣어준다.

for (int i=0;i<nums2Size;i++){
        if (n1[nums2[i]]!=0){
            n1[nums2[i]]--;
            res[cnt++]=nums2[i];
        }
    }

    *returnSize=cnt;
    return res;

Solution

교수님 풀이를 바탕으로 내가 쓴 코드와 교수님 풀이
교수님은 공통원소 여부 판단시에 0과의 대소비교로 진행하셨는데, 나는 어차피 원소가 공통될때마다 1씩 감소시키므로 0과의 등치 여부로 판단했다.
max 부분은 교수님이 실수하신부분으로, min이 맞다.

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

#define MIN(a,b) ((a)<(b)?(a):(b))

int* intersect(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize){
    int *res=(int*)malloc(sizeof(int)*MIN(nums1Size,nums2Size));
    int n1[1001], cnt=0;

    for (int i=0;i<1001;i++) n1[i]=0;

    for (int i=0;i<nums1Size;i++) n1[nums1[i]]++;

    for (int i=0;i<nums2Size;i++){
        if (n1[nums2[i]]!=0){
            n1[nums2[i]]--;
            res[cnt++]=nums2[i];
        }
    }

    *returnSize=cnt;
    return res;
}

Complexity

Time Complexity

$O(N+M)$

Space Complexity

$O(N+M)$

지적과 질문 환영