[알고리즘] LeetCode 3Sum JS

개요

하나의 배열에서 세가지 숫자를 뽑아 0이 되는 경우를 모두 찾는 문제이다. 조합으로 생각하면 쉽다. 순서 상관없이 3가지 숫자를 뽑는데 같은 인덱스에서 3가지를 뽑을 수 없고 이미 만들어진 경우의 수라면 패스한다

3Sum - LeetCode

 

풀이

경우의 수를 구하는 문제를 만나면 왠지 모르게 자꾸 DFS로 접근하게 된다.

 

이번 문제 자체는 세 가지를 뽑아서 비교하는 문제이니 단순히 그리디로 구현한다해도 반복문 3개를 돌려서 풀 수 있었던 부분이지만 말이다. 그래도 구현은 했는데 역시나 시간초과가 발생했고 더 좋은 방식을 고민해보다가 투포인터로 풀 수 있다는 것을 확인했다.

 

DFS로 구현

계속 비교해나가면서 마지막에 sort를 시켜 이미 나왔던 배열인지 확인하는 코드를 짰는데 원본 배열이 정렬되면서 값이 원하지 않는 방식으로 나오면서 조금 삽질했지만 구현은 제대로 하긴했다. 좋지 않은 접근 방식이지만 말이다.

/*
 * @lc app=leetcode id=15 lang=javascript
 *
 * [15] 3Sum
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number[][]}
 *
 * 세 숫자를 뽑아서 0을 만드는 경우를 출력하기
 * DFS?
 */
var threeSum = function (nums) {
  const answer = [];
  const tmp = [];
  const len = nums.length;

  const findUniqueArray = (answerArr, tempArr) => {
    const temp = tempArr.join(",");

    for (let i = 0; i < answerArr.length; i++) {
      const check = answerArr[i].join(",");
      if (check === temp) return false;
    }

    return true;
  };

  const DFS = (start, sum) => {
    if (tmp.length === 3) {
      const sort = [...tmp].sort((a, b) => a - b);
      if (sum === 0 && findUniqueArray(answer, sort)) answer.push(sort);
      return;
    } else {
      for (let i = start; i < len; i++) {
        tmp.push(nums[i]);
        DFS(i + 1, sum + nums[i]);
        tmp.pop();
      }
    }
  };

  DFS(0, 0);

  return answer;
};

 

투 포인터 방식

배열을 정렬시키면 훨씬 간단하게 접근해서 풀어낼 수 있기 때문에 정렬시킨다.

 

3개의 원소를 뽑아야하니 3개의 포인터를 두는데 음수가 나오지 않으면 0을 만들 수 없으니 음수의 범위만 탐색할 수 있도록 한 개를 기준잡아 투포인터를 돌린다.

 

투포인터를 돌리면서 0이 나오면 정답배열에 처리하는데, 이때 배열에 넣고도 정렬에 따라 중복된 값이 있을 수 있으니 중복된 값은 계속해서 넘어간다.

 

0이 아닐때 0보다 작다면 작은 값을 크게 만들고 0보다 크다면 큰값을 작게 만들면서 탐색한다.

투포인터가 만나 기준 값을 중심으로 탐색이 끝났다면 음수의 범위에 있는 기준값을 증가시키면서 탐색을 계속한다. 이때 음수의 범위에 있는 값이 이미 만들어진 경우일 수 있으니 중복된 값들은 패스시킨다. 그 뒤로 다시 탐색을 진행하는 순으로 이어진다.

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
  const answer = [];
  if (nums.length < 3) return answer;
  nums.sort((a, b) => a - b);

  for (let i = 0; i < nums.length - 2; i++) {
    if (nums[i] > 0) return answer; // -값이 나오지않으면 0을 만들 수 없으므로 시작점이 양수가 되는 순간 끝낸다
    let start = i + 1;
    let end = nums.length - 1;

    while (start < end) {
      //중복값이 있는 부분은 넘어간다.
      if (nums[i] + nums[start] + nums[end] === 0) {
        answer.push([nums[i], nums[start], nums[end]]);
        while (nums[start] === nums[start + 1]) start++;
        while (nums[end] === nums[end - 1]) end--;
        start++;
        end--;
      } else if (nums[i] + nums[start] + nums[end] < 0) start += 1;
      else end -= 1;
    }
    //i도 중복을 제거해야한다.
    while (i < nums.length - 3 && nums[i] === nums[i + 1]) {
      i += 1;
    }
  }
  return answer;
};

 

회고

문제를 이해하는데 조금 헷갈렸고 접근 방식이 아쉬웠다.