[Kotlin] Leet Code - 3Sum Closest

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

3Sum Closest - LeetCode

유형

투 포인터

해결 과정

- 구하고자 하는 것

정수 배열에서 세 수의 합 가운데 target에 가장 가까운 것

- 쉽게 떠올릴 수 있는 방법

완전 탐색: 삼중 반복문으로 세 수의 합을 모두 확인한다.

==> 문제: O(n^3)으로 시간 내에 해결함을 보장할 수 없다.

- 시간 복잡도 개선한 방법

1. 배열에서 하나의 숫자(num1)를 선택해서 고정한다. -> O(n)
2. 나머지 수 가운데 num1과 더했을 때 target에 가장 가까운 두 수(num2, num3)를 찾는다.
3. 1번 과정을 모든 숫자에 적용해본다.

2번에서 투 포인터 방법을 사용하면 O(n)으로 두 수를 찾을 수 있다. 따라서 위 과정을 따르기 전에 우선 배열을 정렬한다. 따라서 시간 복잡도 = nlogn(정렬) * n(1번) * n(2번) = O(n^2)

- 투 포인터 사용 과정

기준): target에 가까운 정도

정답) target에 가장 가까운 합 -> 꼭 필요한 변수

과정)

1. 포인터를 오름차순 정렬된 배열의 가장 왼쪽(start)과 오른쪽(end)에 하나씩 둔다.

2-1) if 절대값(target - answer) > 절대값(target - num1 + num2 + num3) -> 정답 갱신

2-2)

if (target > num1 + num2 + num3) -> start++

else if (target > num1 + num2 + num3) -> end--

else -> 정답: num1 + num2 + num3

3. start < end일 때까지 2번 과정 반복

코드 (Kotlin)

import kotlin.math.abs

class Solution {
    fun threeSumClosest(nums: IntArray, target: Int): Int {
        var answerDiffer = Int.MAX_VALUE // 절대값(target - target에 가장 가까운 합)
        var answerSum = 0 // target에 가장 가까운 합
        nums.sort() // 투 포인터로 해결하기 위해 정렬
        
        for (i in 0 until nums.size - 2) {
            var start = i + 1
            var end = nums.lastIndex
            
            while (start < end) {
                val tempSum = nums[i] + nums[start] + nums[end]
                val tempDiffer = abs(target - tempSum)
                
                // target과 차이가 더 작은 합을 발견하면 정답을 갱신
                if (tempDiffer < answerDiffer) {
                    answerDiffer = tempDiffer
                    answerSum = tempSum
                }
                
                if (tempSum > target) {
                    end--
                } else if (tempSum < target) {
                    start++
                } else {
                    return tempSum // 정답은 꼭 하나라고 했으므로 리턴
                }
            }
        }
        
        return answerSum
    }
}

피드백

투 포인터는 정렬된 배열있고 특정 기준이 있을 때, 기준에 가장 부합하는 최적의 두 수를 빠르게 찾을 때 사용할 수 있다. 이분 탐색과 조건이 아주 유사하다.