eetcode - 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로 확 준것을 확인할 수 있었다.
투포인터 방식을 뇌에 한번 기록해보도록 하겠다..
Author And Source
이 문제에 관하여(eetcode - 3sum closest(kotlin)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@mdok1112/leetcode-3sum-closestkotlin저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)