[LeetCode] 016. 3Sum Closest JAVA

3Sum Closest - LeetCode

---

📍 문제

Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target.
Return the sum of the three integers.

길이가 n인 정수 배열 nums와 목표가 정수인 경우 합계가 목표에 가장 근접하도록 nums에서 세 개의 정수를 찾으시오.
세 정수의 합을 반환하시오.

부연 설명 : 길이가 n인 정수의 배열 nums가 주어지면, 그 안에서 합을 구하는 문제이다.

현재 인덱스의 값과 인접한 양 옆의 값을 더 하고, 목표에 가장 근접한 값을 출력하는 문제이다.

---

📍 예시

Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Input: nums = [0,0,0], target = 1
Output: 0
Explanation: The sum that is closest to the target is 0. (0 + 0 + 0 = 0).

---

📍 풀이 설명

• 계산에 용이하도록 배열을 정렬해주었다.
• 비교를 위해 0,1,2 번째 인덱스의 값을 더해주었다.
• 세 값을 비교하기 때문에 반복문에 조건식은 i가 배열의 길이 - 2 보다 작을 때로 해주었다.

 

public static int threeSumClosest(int[] nums, int target) {

   Arrays.sort(nums);
   int result = nums[0] + nums[1] + nums[2];

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

   }

   return result;
}

---

• 세 수의 합이기 때문에 나머지 두 수의 인덱스를 가져오기 위해 변수를 선언해주고 값을 넣어주었다.
• 다시 반복문을 열고, 세 인덱스의 값을 더한 값이 만약 target과 같으면 해당 값을 리턴시켜주었다.
• 만약 더한 값이 target보다 크면 뒤에서부터 세고 있는 right의 값을 마이너스 시켜주고
• 그게 아니라면 left의 값을 플러스 시켜주었다.
• 그리고 target이 안나올 수 있기 때문에 가장 근접값을 구해야했다.
• target에서 sum을 뺀 절댓값이 result를 뺀 절댓값보다 작다면, 더 근접한 숫자이기 때문에 result를 sum으로 바꿔주었다.
• 그리고 반복문이 끝나면 result 값을 리턴시켜 주었다.

public static int threeSumClosest(int[] nums, int target) {

   ...

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

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

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

         if (sum == target) {
            return sum;
         }

         if (sum > target) {
            right--;
         } else {
            left++;
         }

         if (Math.abs(target - sum) < Math.abs(target - result)) {
            result = sum;
         }
      }
   }

   return result;
}

직전에 풀었던 3Sum 문제의 변형이었다.

덕분에 조금 수월하게 생각할 수 있었던 것 같다.

---

📍 최종 풀이

 

public static int threeSumClosest(int[] nums, int target) {

   Arrays.sort(nums);
   int result = nums[0] + nums[1] + nums[2];

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

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

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

         if (sum == target) {
            return sum;
         }

         if (sum > target) {
            right--;
         } else {
            left++;
         }

         if (Math.abs(target - sum) < Math.abs(target - result)) {
            result = sum;
         }
      }
   }

   return result;
}​

---