leetcode 코딩테스트 연습 - 2722. Join Two Arrays by ID (JavaScript)

이번 문제는 객체를 값으로 가지는 두 배열을 합치는 문제였다.

객체의 id값은 유일해야 하고 양 배열에 id가 같으면, 이 객체를 합해야 하는 문제였다.

문제 접근 자체는 어렵지 않았지만, Time Limit Exceeded을 맞이해버렸다.

/**
 * @param {Array} arr1
 * @param {Array} arr2
 * @return {Array}
 */
var join = function(arr1, arr2) {
    const answer = [...arr1];
    const memo = {}
    for(let el of arr2) {
        if(el.id >= 0) {
            let pointer = null;
            if(memo[el.id] >= 0) {
                pointer = memo[el.id];
            } else {
                for(let j = 0; j < answer.length; j++){
                    if(answer[j].id === el.id) {
                        pointer = j;
                        memo[el.id] = j;
                    }
                }
            }
            if(pointer === null) {
                answer.push(el);
            } else {
                // override
                answer[pointer] = {...answer[pointer], ...el};
            }
        } else {
            answer.push(el);
        }
    }
    return answer.sort((a, b) => a.id - b.id);
};

위의 코드가 처음 작성한 코드였는데, 나름 memo 객체를 사용하여 최적화를 하려고 했지만, 역부족이었다.

다시 생각해보면, 초기 arr1을 answer에 넣을 때 함께 memo를 설정하면, 더 빠르지 않을까 싶었다.
🧨 특히 양 배열에 이미 겹치게 id값이 존재 했을 때, 위의 코드는 딱히 memo의 역할이 없었다...

/**
 * @param {Array} arr1
 * @param {Array} arr2
 * @return {Array}
 */
var join = function(arr1, arr2) {
    const answer = [];
    const memo = {};

    for (let i = 0; i < arr1.length; i++) {
        const el = arr1[i];
        answer.push(el);
        memo[el.id] = i;
    }

    for (let el of arr2) {
        if (el.id >= 0) {
            if (memo[el.id] !== undefined) {
                answer[memo[el.id]] = { ...answer[memo[el.id]], ...el };
            } else {
                answer.push(el);
                memo[el.id] = answer.length - 1;
            }
        } else {
            answer.push(el);
        }
    }

    return answer.sort((a, b) => a.id - b.id);
};

그렇게 memo를 다시 최적화하여 코드를 수정하였고, 이번에는 문제를 해결할 수 있었다.

 

🧶 memo를 최적화하는 과정에서 ChatGPT의 도움을 조금 받기도 했는데, 생각보다 더 코드를 잘 분석해주어서 놀랐다. 알고리즘에 있어서는 ChatGPT의 성능이 아주 뛰어난 것 같다.

 

처음에 if문 조건에 숫자가 들어간 변수를 생각없이 계속 넣었었는데, id가 0일때 false로 판별하여 문제가 되었었다.

늘 생각하지만, 조심해야하는 부분이다.