leetcode - 3sum closest(kotlin)

level - medium

[문제 내용]
배열중 3개의 숫자를 더한 값이 target과 가장 가까운 값을 구하라

[example 1]

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).

[해결 방법]
먼저 이 문제를 2가지 방법으로 풀어보았다.

지금 설명할 것이 처음에 머리에 딱 떠오른대로 푼 방법이다.
3개를 골라서 합을 구해야하기 때문에
조합을 이용해서 3개를 고르기로 결정했다.
여기서 조합으로 모든 3개의 경우의 수를 구하면
시간 초과가 날것 같아서 배열을 정렬하고
그 정렬된 배열에서 3개를 뽑아서 그 3개의 합과 target의 차가 0이면
더이상 찾지않고 나오는 방식으로 진행하였다.

import kotlin.math.abs

class Solution {
    var min = Int.MAX_VALUE
    var sumOfThree = 0
    fun threeSumClosest(nums: IntArray, target: Int): Int {
        nums.sort()
        combination(nums, IntArray(3), 3, 0, 0, target)
        return sumOfThree
    }

    fun combination(arr: IntArray, result: IntArray, r: Int, current: Int, start: Int, target: Int) {
        if(r == current) {
            var sum = 0
            for(r in result) {
                sum += r
            }

            val difference = abs(sum - target)
            if(difference < min) {
                min = difference
                sumOfThree = sum
            }

            return
        }
        
        if(min == 0) {
            return
        }

        for(i in start until arr.size) {
            result[current] = arr[i]
            combination(arr, result, r, current+1, i+1, target)
        }
    }
}

이렇게 진행 하였을 경우, 272ms가 걸리는 것을 확인했다.

제출후 저 시간 분포도를 보고 이렇게 푸는 것이 아님을 직감하고
솔루션을 보고 다시 풀어보았다.

two-pointer 방식으로 문제를 해결하는 것이었는데,
위와 아래에서 차례로 훑어가면서
3개의 합을 구해 가장 차가 작은 것을 구하는 방식이었다.

import kotlin.math.abs

class Solution {
    fun threeSumClosest(nums: IntArray, target: Int): Int {
        var difference = Int.MAX_VALUE
        nums.sort()

        for(i in nums.indices) {
            if(difference == 0) {
                break
            }

            var low = i+1
            var high = nums.size-1
            while(low < high) {
                val sum = nums[i] + nums[low] + nums[high]
                if(abs(target-sum) < abs(difference)) {
                    difference = target - sum
                }

                // 배열이 정렬되어 있는것을 잊지말자
                if(sum < target) {	// 합이 target보다 작으니까 아래에서 위로 올라가기
                    ++low
                } else {	// 합이 target보다 크니까 위에서 아래로 내려가기
                    --high
                }
            }
        }

        return target-difference
    }
}

위와 같이 다시 풀어서 제출하였을 땐, 192ms로 확 준것을 확인할 수 있었다.

투포인터 방식을 뇌에 한번 기록해보도록 하겠다..