[LeetCode] #16 - 3Sum Closest

이번 문제는 3Sum문제와 유사하지만 3개정수의 합이 입력받은 target에 가까운 수의 정수를 리턴하는 문제이다.

난의도 : ★★★☆☆

Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Given array nums = [-1, 2, 1, -4], and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

먼저 의사코드를 작성하면 아래와 같다.

1. 입력받은 수들을 오름차순 정렬한다.
2. 근사값에 정수의 최대값을 할당한다.
     최대값을 할당하면 처음 합과 비교할때 무조건 크기때문에 
      조건문에서 초기값을 설정할 수 있다.
3. 입력받은 리스트에서 -2만큼 순회한다.
    4. 첫번째 포인트를 0으로 초기화
    5. 두번째 포인트를 세번째포인트 - 1으로 초기화
    6. 세번째 포인트를 2로 초기화
    7. 첫번째 포인트보다 두번째 포인트가 클동안 순회한다.
        8. 합계 = 리스트[첫] + 리스트[두] + 리스트[세]
        9. 찾는값 타겟이 합계와 같으면 타겟을 리턴하고 종료한다.
        10. 현재 합계가 타겟에 가장 가까운 값인경우 근사값에 절대값(합계-타겟)를  
            설정하고 결과값에 합계를 설정한다.
        11. 타겟이 합계보다 크면 첫번째 포인트를 증가시킨다.
        12. 아니면 두번째 포인트를 감소시킨다.
13. 결과값을 리턴한다. 

코드로 구현하기 (파이썬)

class Solution:
    def threeSumClosest(self, nums, target):
        nums.sort()
        closest = float('inf')
        for p in range(2, len(nums)):
            l = 0
            r = p - 1
            while l < r:
                sum = nums[l] + nums[r] + nums[p]
                if target == sum: return target
                if abs(target-sum) < closest:
                    closest = abs(target-sum)
                    res = sum
                if target > sum: l += 1
                else : r -= 1
     return res

• 파이썬에서는 정수의 MAX값이 존재하지 않지만 공식적으로 최대값을 구하는 방법은
  라이러리를 이용한 sys.maxint - 1이다. 이 링크에서 확인할 수 있다.
  하지만 라이브러리 이용은 가급적 피하고 싶어서 무한수flost('inf')를 이용하였다.

실행해보면 테스트케이스 125를 통과한 결과 124 ms가 나오는 것을 확인 할 수 있다.
시간복잡도는 O(n^2) 이다.