.leetcode(16. 3Sum Closest)

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

 

1. 2022.01.30 시도

소요시간: 27분(5분 구상, 22분 코딩)

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        
        Arrays.sort(nums);
        int output = 5000;
        for (int i=0; i<nums.length; i++) {
            int subTarget = target - nums[i];
            
            // two sum
            int left = i+1;
            int right = nums.length - 1;
            int sum = 5000;
            while (left < right) {
                int temp = nums[right] + nums[left];
                if (temp == subTarget) {
                    return target;
                } else if (temp < subTarget) {
                    sum = judgeSum(nums, subTarget, sum, temp);
                    left++;
                } else if (temp > subTarget) {
                    sum = judgeSum(nums, subTarget, sum, temp);
                    right--;
                }
            }
            
            output = judgeSum(nums, target, output, nums[i]+sum);
        }
        
        return output;
    }
    
    private int judgeSum(int[] nums, int target, int sum, int temp) {
        if (Math.abs(target - temp) < Math.abs(target - sum)) {
            return temp;
        }
        
        return sum;
    }
}

풀이 접근 과정

3가지 합이므로 이를 2가지합 문제로 풀려면 하나를 선택하고 그 외의 값내에서 포인터 2개를 써서 근사치의 값을 구하는게 필요하다고 생각했다. 

정렬에 O(nlogn)이 들고 실제로 위의 로직을 구현하면  n^2이 드니 결국 시간복잡도는 O(n^2)으로 생각되었다. 느리지만 그래도 지금 구성으로는 이게 최선의 복잡도라고 생각하여 문제를 풀었다.

범위를 보니 3개의 합을 해도 최대 -3000 ~ 3000이기때문에 디폴트가 필요한건 5000으로 세팅해두고 풀엇다.

 

느낀점

• 이전에 twosum문제를 풀면서도 시간이 오래걸려 쉽사리 도전하지 못했다. 구상시간이 너무 오래걸리기전에 바로 풀었다. 다행이도 솔루션도 똑같은 시간복잡도를 갖고 있었다. 이게 최선이엇나보다.
• 3개의 합이기 때문에 하나의 요소를 잡아두면 twosum으로 풀 수 있겠다 싶었다. twosum 풀이는 https://silvergoni.tistory.com/entry/leetcode167-Two-Sum-II-Input-Array-Is-Sorted를 상기하면서 풀엇다. left, right를 두고 근사치를 계산하면서 풀이했다.
• 처음에는 모든 요소를 계산했었는데 하다보니 i번째의 요소 이하는 중복계산되므로 할 필요가 없다는걸 깨닫게 되었다.
• 2가지가 포인트였다. 하나는 요소를 하나선택해서 twosum문제로 만드는 것이고 두번째는 중복을 피하기 위해 i+1부터 시작하는 것이었다.

---

알고리즘 정리노트: .leetcode(알고리즘 문제풀이 접근)

반응형