[LeetCode] 3Sum (javascript)

주어진 숫자 배열에서 3개의 숫자를 조합하여 0이 되는 조합을 찾아내는 문제다.

 

1. 같은 숫자가 여러개 있다면, 여러번 사용되어도 된다.

2. 결과 조합에는 중복이 없어야 한다.

 

코드가 굉장히 지저분하게 작성되었다ㅜㅜ 3중 포문이 웬말이냐...

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
    nums.sort((a, b) => a - b); // 오름차순 정렬

    // 0을 제외하고, 중복되는 숫자는 최대 2개만 있어도 된다.
    const uniq = [...new Set(nums)];
    const newArr = [];
    for (let i = 0; i < uniq.length; i++) {
        const first = nums.indexOf(uniq[i]);
        const last = nums.lastIndexOf(uniq[i]);
        if (first == last) {
            newArr.push(uniq[i]);
        } else if (uniq[i] == 0 && first + 1 < last) {
            newArr.push(0, 0, 0);
        } else {
            newArr.push(uniq[i], uniq[i]);
        }
    }
    
    const firstPositive = newArr.findIndex((num) => num > 0);
    // 양수가 없는 경우, triplet이 존재하지 않거나, [0, 0, 0] 뿐이다.
    if (firstPositive === -1) {
        if (newArr.filter((num) => num == 0).length > 2) {
            return [[0, 0, 0]];
        }
        return [];
    }

    const result = [];
    let isZeroTripletAdded = false;
    for (let i = 0; i < newArr.length; i++) {
        if (i >= firstPositive) continue; // 양수끼리만 조합된 경우 찾을 필요 없다.
        for (let j = i + 1; j < newArr.length; j++) {
            for (let k = j + 1; k < newArr.length; k++) {
                if (k < firstPositive - 1) continue; // 음수끼리만 조합된 경우 찾을 필요 없다.
                if (newArr[i] + newArr[j] + newArr[k] == 0) {
                    if (newArr[i] == 0 && newArr[k] == 0 && !isZeroTripletAdded) {
                        result.push([0, 0, 0]);
                        isZeroTripletAdded = true;
                    }
                    if (!isDuplicated(result, [newArr[i], newArr[j], newArr[k]]))
                        result.push([newArr[i], newArr[j], newArr[k]]);
                }
            }
        }
    }
    return result;
};
const isDuplicated = (origin, newArr) => {
    return origin.some(
        (o) => o.includes(newArr[0]) && o.includes(newArr[1]) && o.includes(newArr[2])
    );
};

 

처음엔 찾을 필요 없는 제외 코드를 적지 않았다가, Time limit에 걸리는걸 보고 아래 내용을 추가했다.

- 3개의 숫자를 조합하므로, nums배열은 0은 최대 3개, 다른 숫자는 최대 2개만 빼고 삭제해도 무관하다.

  - 0+0+0 = 0, 2 + 2 + -4 = 0 이므로...

- 양수끼리만 조합된 경우 찾을 필요 없음

- 음수끼리만 조합된 경우 찾을 필요 없음

 

 

추후 좀 더 개선해 봐야겠다..

 

 

 

https://leetcode.com/problems/3sum/