LeetCode 2215. Find the Difference of Two Arrays

 

나중에 잊을 때쯤 다시 풀어볼 문제

더블포인터...힝

 

초기 접근 방법

❗️처음에 생각한 방향

 

주어진 두 배열의 공통이 아닌 숫자를 각각 출력하는 문제로,

가장 처음 생각난 건, Brute Force 방법

즉, 반복문을 중첩해서 다 조회하는 것.

 

코드는 머리로도 금방 구현이 되나 어차피 Time Limit Exceeded가 뜰 것을 알기에..

구현하지 않음

 

 

 

 

최종 접근

해시테이블 알고리즘을 공부하기 위해 푼 문제로

처음부터 어떻게 하면 해시테이블을 사용할 수 있을까

왜 이 문제는 해시테이블이어야만 할까를 초점으로 고민해서 접근

 

 

✅ 해시테이블은 키값으로 한 번에 데이터를 조회할 수 있는 자료구조로

자료 검색을 굉장히 빠르게 할 수 있다는 장점이 있음 (이미 테이블이 정리가 되어 있다고 가정했을 때)

 

 

✅ 이 문제를 풀기위한 자료구조로 왜 해시테이블이어야 하는가?

1. 1번 배열이 2번 배열의 자료를 검색해야하는 구조에서 빠르게 조회할 수 있음 (역으로도 성립)

2. 숫자를 키값으로 두고, value값을 (0 or 1)중복 여부로 둘 수 있음

3. 배열에 들어갈 수 있는 숫자 범위가 정해져 있고, 크지 않음

• -1000 <= nums1[i], nums2[i] <= 1000

4. 판단하기에 해시테이블을 이용해 시간복잡도가 적은 방법으로 해결할 수 있다고 판단

 

✅ 위에 숫자 범위가 정해져 있으나, 배열의 인덱스가 음수가 될 수 없다는 점을 이용해

인덱스에 규칙을 만듦.

먼저, 주어지는 숫자의 범위가 -1000부터 1000이므로 해시테이블의 크기는 2001 ( = 1000 - (-1000) +1 )

위와 같이 지정한 이유는 배열이 가지고 있는 숫자를 Key로 두고, (이게 주어진 조건에 의해 위 범위가 될 수 있음)

해당 숫자를 가지고 있는 지에 대한 여부를 Value로 둘 것이기 때문

 

 

✅ 만일, nums[i] < 0 이라면, 해당 값에 2001 만큼 더한 키값으로 저장

예) nums[1] = -10 이라면, HashTable1[-10]은 유효하지 않은 배열이므로

-10 + 2001 = 1991한 값이 키값이 된다.

이렇게 함으로써 nums[i] > 0 인 값과 중복되지 않게 한다.

(애초에 범위가 1000까지 이기 때문에 1991인 값을 갖을 수 없음)

 즉, 위와 같은 경우 HashTable[1991] = 1 이 된다.

 

 

✅ 이미 ret arr에 들어간 숫자는 중복되어 들어가지 않도록 value값을 1로 바꿔준다

 

 

 

 

처음 코드

int** findDifference(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize, int** returnColumnSizes){
    *returnSize = 2;
    *returnColumnSizes = (int*)malloc(2*sizeof(int));

    int** ret = (int**)malloc((sizeof(int*) * 2));
    ret[0] = (int*)malloc(nums1Size* sizeof(int));
    ret[1] = (int*)malloc(nums2Size* sizeof(int));

    int HT1[2001] = {0,};
    int HT2[2001] = {0,};
    for(int i=0; i<nums1Size; i++){
        if(nums1[i]>=0) HT1[nums1[i]] = 1;
        else HT1[nums1[i]+2000] = 1;
    }
    
    for(int i=0; i<nums2Size; i++){
        if(nums2[i]>=0) HT2[nums2[i]] = 1;
        else HT2[nums2[i]+2000] = 1;
    }

    int j=0;
    for(int i=0; i<nums2Size; i++){
        if(HT1[nums2[i]] != 1){
            ret[1][j++] = nums2[i];
            HT1[nums2[i]] = 1;
        }
    }
    (*returnColumnSizes)[1] = j;  

    j=0;
    for(int i=0; i<nums1Size; i++){
        if(HT2[nums1[i]] != 1){
            ret[0][j++] = nums1[i];
            HT2[nums1[i]] = 1;
        }
    }
    (*returnColumnSizes)[0] = j; 

    return ret;
}

 

처음에는 2001이 아니라 2000을 더해서 중간에 의도한 output이 나오지 않음

 

✏️ 2000을 더할 시 문제가 되는 부분은

만일, nums[i] = -1000일 때, 2000을 더하면 1000이 되는 데,

이는 처음부터 nums[k] = 1000인 값과 범위가 겹치게 된다.

따라서 2001을 더하는 것이 맞음.

 

 

 

 

 

구현

Runtime : 40ms

Beats 100.00% of users with C

int** findDifference(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize, int** returnColumnSizes){
    *returnSize = 2;
    *returnColumnSizes = (int*)malloc(2*sizeof(int));

    int** ret = (int**)malloc((sizeof(int*) * 2));

    ret[0] = (int*)malloc(nums1Size* sizeof(int));
    ret[1] = (int*)malloc(nums2Size* sizeof(int));

    int HT1[2001] = {0,};
    int HT2[2001] = {0,};
    for(int i=0; i<nums1Size; i++){
        if(nums1[i]>=0) HT1[nums1[i]] = 1;
        else HT1[nums1[i]+2001] = 1;
    }
    
    for(int i=0; i<nums2Size; i++){
        if(nums2[i]>=0) HT2[nums2[i]] = 1;
        else HT2[nums2[i]+2001] = 1;
    }

    int j=0;
    for(int i=0; i<nums2Size; i++){
        if(nums2[i]<0){
            if(HT1[nums2[i]+2001] != 1){
                ret[1][j++] = nums2[i];
                HT1[nums2[i]+2001] = 1;
            }
        }
        else{
            if(HT1[nums2[i]] != 1){
                ret[1][j++] = nums2[i];
                HT1[nums2[i]] = 1;
            }
        }
    }
    (*returnColumnSizes)[1] = j;  

    j=0;
    for(int i=0; i<nums1Size; i++){
        if(nums1[i]<0){
            if(HT2[nums1[i]+2001] != 1){
                ret[0][j++] = nums1[i];
                HT2[nums1[i]+2001] = 1;
            }
        }else{
        if(HT2[nums1[i]] != 1){
            ret[0][j++] = nums1[i];
            HT2[nums1[i]] = 1;
        }
        }

    }
    (*returnColumnSizes)[0] = j; 

    return ret;
}

 

위 코드에서 2001로 바꾸니까 완벽하게 실행되는 것을 확인할 수 있었음.

Runtime 1등 Memory 좋음좋음

 

코드 자체가 길고 for 문이 여러개 있기는 해도

1. 중첩된 반복문이 없고,

2. 자료구조 자체가 빠른 검색이 되는 자료형이라서

런타임에서 1등한 것을 확인 가능 ! ㅎㅎ

 

 

그리고 LeetCode의 경우, 코드 자체는 맞게 구현하고, 알고리즘 자체는 맞게 구현해도

특정 코드라인이 삽입되지 않으면 output이 나오지 않는 문제가 있음

 

(*returnColumnSizes)[0] = j; 
(*returnColumnSizes)[1] = j;

 

이 문제에서는 위 라인이 그랬음.

이 부분에 대해서는 조금 더 구체적이고 정확한 코드를 짜기 위해서 노력해야할 듯 !

 

 

 

내꺼 제출하고 다른 사람 코드 구경하다가 깔끔하게 구현해놨다고 생각이 되어 들고온 것

기본적인 모든 알고리즘이나 구현 순서는 나와 유사하나

디테일적인 부분에서 굿굿

memory를 적게 사용한다던지,, 애초에 0으로 초기화되는 calloc을 사용한다던지,, 등등

 

int** findDifference(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize, int** returnColumnSizes){
    returnColumnSizes[0] = calloc(2, sizeof(int));
    *returnSize = 2;
    
    int **ret = malloc(sizeof(int*) * 2);
    ret[0] = malloc(sizeof(int) * 1000);
    ret[1] = malloc(sizeof(int) * 1000);
    int *table = calloc(2001,sizeof(int));
    
    for (int i = 0; i < nums2Size; i++)
        table[nums2[i] + 1000]++;
    
    for (int i = 0; i < nums1Size; i++){
        if (table[nums1[i] + 1000] == 0)
            ret[0][returnColumnSizes[0][0]++] = nums1[i];
        table[nums1[i] + 1000] = -1;
    }
    
    for (int i = 0; i < 2001; i++)
        if (table[i] > 0)
            ret[1][returnColumnSizes[0][1]++] = i - 1000;
    
    free(table);
    return ret;

 

 

 

Take aways

✅ 아래와 같은 경우에 해시테이블 자료구조를 사용해보자!

1. 여러 번의 자료 검색이 필요할 때

2. 많은 양의 자료 검색이 필요할 때

3. 자료 범위가 크지 않고 정해져 있을 때

4. 중복되는 자료가 있을 가능성이 존재할 때

5. Key-Value 값이 명확할 때

 

 

✅ 음수인 값을 배열의 인덱스로 넣고 싶을 때는 규칙을 만들어서 넣어보자!

음수인 값에 특정 값을 더해서 배열에 넣기 가능

이 때, 배열의 인덱스가 겹치지 않도록 범위 설정에 주의하자

 

 

✅ calloc은 자동으로 0으로 초기화해줌 !! 필요한 순간에는 깔끔한 코드로 구현 가능할 듯