[LeetCode] 3Sum 개인 풀이

문제

Integer로 주어지는 배열이 있습니다. 해당 배열의 요소중 3개를 선택해서 합이 0이 만들어지는 경우를 출력하세요. 중복된 경우는 한번만 출력합니다.

예제 1
입력: nums = [-1,0,1,2,-1,-4]
출력: [[-1,-1,2],[-1,0,1]]

예제 2
입력: nums = []
출력: []

예제 3
입력: nums = [0]
출력: []

• 제약조건
  nums의 길이는 0 ~ 3000까지 가능
• 10^5 <= nums[i] <= 10^5

원본 : leetcode_3Sum

개인 풀이

• nums의 갯수가 3000개까지가 가능하기때문에 O(N^2)에 대해서는 900만 연산으로 괜찮은 속도를 유지할 수 있습니다. 하지만 N^3이라면 270억 연산으로 문제가 있습니다. 따라서 우리는 N^2 또는 맥스 N^2 * logN 정도의 시간복잡도안에 문제를 해결할 수 있도록 해야합니다. (3가지 수의 합을 다 찾아보는건 N * N * N의 시간이 걸리므로 시간 오버입니다.)
• 합이 0이 되기 위해서는 음수와 양수를 합해야합니다.
• 0, 0, 0 도 있을 수 있습니다. ( 예외사항 )

먼저 N^3이 아니게 합이 0인 3개의 숫자를 구하는 방법으로 정렬한 후 하나의 값을 선정 후 그 값이 나머지 3개의 합과 0이 되게 하면 되지 않을까? 하고 생각해보았습니다.

예를 들어 [-1,0,1,2,-1,-4]라면 정렬했을 경우 [-4, -1, -1, 0, 1, 2] 이며 -4는 결과값이 없으므로 -1이 나머지 두개와의 합이 0이 되는 걸 찾는다고 하면 0과 1이라는 값이 도출되면 된다는 것을 알 수 있습니다.

여기서 0과 1이라는 값을 N의 시간동안 어떻게 가져올 수 있을까요 ? 퀵정렬처럼 left와 right 기준을 주고 범위를 좁혀가며 찾는다면 가능할 것으로 보였습니다. 그리고 찾는 범위 또한 본인보다 왼쪽의 값은 더하면 더욱 음수의 절대값이 커지기때문에 무시해도 된다는 점도 연산횟수를 줄이는데 역할을 합니다.

지정된 값을 sums[select]라고 하고 왼쪽 부터 찾는것을 sums[left], 오른쪽 부터 찾는것을 sums[right]라고 하겠습니다.

• sums[select] = sums[left] + sums[right] 가 만족하면 이 값은 정답중 하나라는 것입니다. 해당 값을 저장 후 left는 1올리며 right는 1내립니다.
• sums[select] > sums[left] + sums[right] 라면 sums[left]가 값이 좀 더 높아야 만족할 수 있으므로 left의 값을 1 올려줍니다.
• sums[select] < sums[left] + sums[right] 라면 sum[right]가 값이 너무 크다는 의미로 값을 1을 줄여줍니다.

left와 right가 겹치거나 교차되면 더이상 값은 없다는 것입니다. 이렇게 연산하면 기준값에 대해서 N의 속도로 문제를 해결 할 수 있습니다.

결과적으로 N^2의 연산으로 문제를 해결할 수 있게 되는 것입니다.

코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {

    if (nums.length <= 2) {
      return Collections.emptyList();
    }

    Arrays.sort(nums);

    int zeroIndex = -1;
    for (int i = 0; i < nums.length; i++) {
      if (nums[i] >= 0) {
        zeroIndex = i;
        break;
      }
    }

    if (zeroIndex < 0) {
      return Collections.emptyList();
    }


    Set<List<Integer>> result = new HashSet<>();
    for (int i = 0; i <= zeroIndex ; i++) {

        if (i != 0 && nums[i] == nums[i - 1])
        continue;

      int left = i + 1;
      int right = nums.length - 1;

      while(left < right) {

        if (nums[left] + nums[right] + nums[i] < 0) {
          left++;
        } else if (nums[left] + nums[right] + nums[i] == 0) {
          List<Integer> subResult = new ArrayList<>();
          subResult.add(nums[i]);
          subResult.add(nums[left]);
          subResult.add(nums[right]);
          result.add(subResult);
          left++;
          right--;
        } else {
          right--;
        }
      }

      if (nums[i] == 0) {
        if (nums.length - i > 2 && nums[i + 1] == 0 && nums[i + 2] == 0) {
          result.add(Arrays.asList(0, 0, 0));
        }

        return new ArrayList<>(result);
      }
    }

    return new ArrayList<>(result);
  }
}

마무리

어떻게 중복 연산을 줄일 수 있을지가 이 문제의 속도를 높이는 핵심이라고 생각하게 되었습니다.

저는 값의 중복을 없애려고 Set을 사용했는데 알고리즘적으로 해결할 수 있는 방법으로 풀 수 있다면 더 높은 성능적인 점수를 얻을 수 있을 것이라고 생각합니다.

감사합니다.