[리트코드] 16. 3Sum Closest

안녕하세요. 개발조각입니다.😊

이번 문제는 15번 문제의 응용 버전인 것 같아요.

15번을 이해하셨으면 쉽게 풀었을 것 같고,

16번 답안이 15번 코드와 90% 정도 똑같은 것 같아요.

---

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

3Sum Closest - LeetCode

 

해결방안

var threeSumClosest = function(nums, target) {        
    nums.sort((a,b)=>a-b);
    let answer = nums[0] + nums[1] + nums[nums.length-1];    

    for(let i=0; i<nums.length-2; i++){
        if(nums[i] === nums[i-1]) continue;
        
        let [point, start, end] = [i, i+1, nums.length-1];
        
        while(start < end){
            let sum = nums[point] + nums[start] + nums[end];

            if(sum < target) start++;
            else if(sum > target) end--;
            else return target;
            
            let [answerAbs, sumAbs] = [Math.abs(answer-target), Math.abs(sum-target)];            
            if(answerAbs < sumAbs) continue;
            else answer = sum;
        }        
    }    
    return answer;
};

 

nums.sort((a,b)=>a-b);

먼저 정렬을 해줍니다.

정렬을 해주는 이유는 3개의 수의 합이 sum이라 하면

sum이 targt보다 작거나, 크거나, 같을 경우에 따라 제어해줄 거라 무조건 정렬을 해줘야 됩니다.

 

let answer = nums[0] + nums[1] + nums[nums.length-1];

answer은 target에 가장 가까운 숫자를 구해줄 변수입니다.

여기서는 let answer = 0;이라고 안 쓰고 실제로 3개의 수를 더했을 때의 합을 넣어 주었습니다.

target이 0일 경우도 있고 등등의 문제가 있어서 실제로 3개의 수를 더했을 때의 합을 넣어 주었습니다.

 

for(let i=0; i<nums.length-2; i++){
    if(nums[i] === nums[i-1]) continue;

    let [point, start, end] = [i, i+1, nums.length-1];

    while(start < end){
        let sum = nums[point] + nums[start] + nums[end];

        if(sum < target) start++;
        else if(sum > target) end--;
        else return target;

        let [answerAbs, sumAbs] = [Math.abs(answer-target), Math.abs(sum-target)];            
        if(answerAbs < sumAbs) continue;
        else answer = sum;
    }        
}

15번 문제와 똑같이

for문으로 point를 이동시킬 거고

while문으로 start, end를 이동시켜줍니다.

 

규칙은 아래와 같이 진행이 됩니다.

• sum < target → start++
• sum > target → end++
• sum === target → 다른 값을 구할 필요가 없기 때문에 return을 해준다.

 

15번 문제와 유사하지만 다른 점

sum === target일 경우

else return target;

 

만약 이전에 만든 sum값(즉 answer) 이 현재 sum값보다 target에 가까운 경우

다음으로 넘겨줍니다.

아닐 경우 answer을 현재 sum값으로 바꾸어 주면 됩니다.

let [answerAbs, sumAbs] = [Math.abs(answer-target), Math.abs(sum-target)];            
if(answerAbs < sumAbs) continue;
else answer = sum;