LeetCode: 15번 (3Sum) [JAVA]

문제 링크

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

3Sum - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

 

1. 주어진 nums 배열을 오름차순 정렬
2. 주어진 nums 배열의 처음부터 끝 - 2까지를 반복문을 돌며, 해당 수(i)와 그 다음 수(j) 그리고 nums 배열 끝의 마지막 수(k)까지 총 3개를 뽑아 탐색을 시작
3. 뽑은 3개의 수(nums[i] + nums[j] + nums[k])를 합해 sum을 계산하여 이후 동작을 실행
   1. 만약 해당 결과가 0이고, 기존 답안의 중복이 아니라면 답안 ArrayList에 추가 후 ++j, ++k
   2. 합이 0보다 크면 --k;
   3. 합이 0미만 이라면 ++j
4. j < k일때 까지 while문으로 앞의 3과정을 반복
5. 정답 List<List<Integer>>를 반환

 처음 문제를 보았을 때는 3개의 수를 뽑아 그 합이 0이 되는 것을 모두 반환하면 되기에 단순히 조합을 사용하여 주어진 nums에서 3개의 수를 뽑는 형태로 풀이를 진행했더니 시간초과가 발생하였다. 그렇다보니 조합보다 훨씬 적은 가짓수로 탐색을 해야 하는데, 이 때 수들을 정렬하여 탐색을 하는 형태로 계산 횟수를 줄일 수 있다.

 우선 주어진 nums 배열을 정렬한 후, 배열의 처음부터 끝 - 2 까지를 반복문을 돌며 3개 수 중의 첫 번째인 i로 정한다. 그리고 i + 1인 값을 j로, 구간의 마지막을 k로 탐색을 시작하는데, 3개 수의 합인 nums[i] + nums[j] + nums[k]를 바탕으로 그 다음 동작을 진행한다. 만약 합이 0이라면 단순히 기존 답안 리스트에 중복되는지 아닌지를 확인하고 답안을 추가한 다음, ++j와 --k를 통해 다음 탐색을 이어간다. 그 외의 경우엔 탐색의 횟수를 줄이기 위해 k와 j를 바꿔가면서 탐색을 하는데, 만약 합이 0 초과라면 하나의 수를 더 작게 만들어야 하기 때문에 가장 마지막에 있는 k를 하나 빼는 형태로, 합이 0 미만이라면 하나의 수를 더 크게 만들어야 하기 때문에 정해진 i를 제외하고 두 번째에 있는 j를 하나 더하는 형태로 만든 다음 다음 탐색을 진행한다. 그렇게 j와 k를 바꾸어가면서 j < k를 만족할때까지만 탐색을 반복하면 횟수를 크게 줄일 수 있다.

 그렇게 탐색을 완료하고 나서 기존의 답안을 추가한 List<List<Integer>> answer를 반환하면 된다.

 

class Solution {
    List<List<Integer>> answer = new ArrayList<>();
    HashSet<String> answerHashSet = new HashSet<>();

    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);

        for (int i = 0; i < nums.length - 2; i++) {//시작부터 끝-2까지
            int j = i + 1;
            int k = nums.length - 1;

            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];

                if (sum == 0) {//결과가 0이라면
                    if (!answerHashSet.contains(nums[i] + "-" + nums[j] + "-" + nums[k])) {//중복이 없다면
                        answerHashSet.add(nums[i] + "-" + nums[j] + "-" + nums[k]);
                        answer.add(List.of(nums[i], nums[j], nums[k]));
                    }
                    ++j;
                    --k;
                } else if (sum > 0) {//합이 0초과
                    --k;
                } else {//합이 0미만
                    ++j;
                }
            }
        }

        return answer;
    }
}

결과