리트코드에서 3Sum 문제를 풀어봤다

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.

영어를 잘 못하지만 대충 해석해보자면...

정수형 배열이 주어지고, 숫자 3개를 더해서 0이 되는 조합을 찾아내면 되는 것이다!

처음에 문제를 잘못 이해하고 Set을 사용해서 문제를 해결하려 했지만 그렇게 하면 중복이 제거가 돼서 답이 나오지 않는 문제가 있어 방식을 변경하게 되었다!

public List<List<Integer>> threeSum(int[] nums) {
        List<Integer> sorted = new ArrayList<>(Arrays.stream(nums).boxed().toList());
        Collections.sort(sorted);

        Set<List<Integer>> result = new HashSet<>();

        for (int i = 0; i < sorted.size() - 2; i++) {
            for (int j = i + 1; j < sorted.size() - 1; j++) {
                for (int k = j + 1; k < sorted.size(); k++) {
                    if (sorted.get(i) + sorted.get(j) + sorted.get(k) == 0) {
                        List<Integer> zeroList = Arrays.asList(sorted.get(i), sorted.get(j), sorted.get(k));
                        Collections.sort(zeroList);
                        result.add(zeroList);
                    }
                    if (sorted.get(i) + sorted.get(j) + sorted.get(k) > 0) {
                        break;
                    }
                }
            }
        }

        return new ArrayList<> (result);
    }

그렇게 변경한 방식은 3중 for문을 통해서 모든 배열을 훑으며 검사를 하는 정말 단순한 방식이었다.

하지만 O(n^3) 이라서 시간초과가 발생했다...

그래서 다른 방법을 고민해봤는데 개선된 방법이 2중 for문을 사용해서 문제를 해결하는 방법이다.

public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    Set<List<Integer>> result = new HashSet<>();


    for (int i = 0; i < nums.length - 2; i++) {
        int right = i + 1;
        int left =  nums.length - 1;

        while(right < left){
            int sum = nums[i] + nums[right] + nums[left];

            if (sum == 0) {
                result.add(Arrays.asList(nums[i], nums[right], nums[left]));
                right++;
                left--;
            } else if (sum < 0) {
                right++;
            } else {
                left--;
            }
        }
    }

    return new ArrayList<> (result);
}

바로 하나를 정해놓고 오른쪽과 왼쪽으로 보내서 중간에 만나게 하는 방법이다

0부터 시작해서 좌우를 구해서 더한 후 0이면 Set에 추가하고, 만약 합이 0보다 작다면 좀 더 큰 수를 더해야 하니까 right를 1증가시켜보고 0보다 크다면 좀 더 작은 수를 더해야 하니까 left를 1 감소시켜보는 방식으로 진행했다

이렇게 하니 2중 for문으로 줄어서 통과했다!

근데 좀 많이 느렸다...

하지만 할일이 많으니까 최적화는 다음에 해보도록 하자.
바쁘다 바빠

끝