3Sum Closest
LeetCode 16번 문제
https://leetcode.com/problems/3sum-closest/
3Sum Closest - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
1. 문제
Given an integer array nums of length n 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.
정수의 배열 nums에서, 세 정수의 합이 주어진 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).
Example 2:
Input: nums = [0,0,0], target = 1
Output: 0
Constraints:
- 3 <= nums.length <= 1000
- -1000 <= nums[i] <= 1000
- -104 <= target <= 104
2. 풀이
■ 풀이 방법
세 가지 정수를 선택하는 모든 경우의 수를 탐색하는 방법으로 이 문제를 풀기에는 시간 초과가 걸린다.
따라서 다음과 같은 방법을 사용한다.
정수 하나를 선택한다.
선택된 숫자를 제외하고 Two Pointer 방식을 사용해서 합이 target값과 가장 근사한 값이 되는 정수 2개를 탐색한다.
□ Two Pointer 방식
주어진 정수의 배열에서 두가지 숫자의 조합을 전부 구하는 것 역시 비효율적이다 따라서 Two Pointer 방식을 사용한다.
다음과 같은 과정을 통해 정수의 배열 n에서 target값 M과 가장 근사한 두 수의 합의 조합을 찾을 수 있다.
정수의 배열 n을 오름차순으로 정렬한다.
배열 n의 첫번째 인덱스를 start로, 마지막 인덱스를 end로 설정한다.
[정렬된 배열과 start, end]
이후에는 다음과 같은 규칙에 의해 start와 end를 이동시킨다.
n[start] + n[end] < M
=> start++
n[start] + n[end] >= M
=> end--
start == end라면 탐색 종료
위의 방식으로 target값 M에 근접하는 방식으로 start와 end를 이동시키며 합이 M과 가장 근사한 두 정수를 찾는다.
□ 증명
앞에서 설명한 Two Pointer방식은 target값 M에 대해 start와 end를 이동시키며 가장 근사한 값을 찾는다.
n[start]와 n[end]의 합이 M보다 작을 때에는 start에 +1을 하는 것으로 n[start] + n[end] 값을 늘리는 것으로 M에 근사하게 된다.
반대의 경우에는 end에 -1을 하는 것으로 값을 줄여 M에 근사시킨다.
※ 오름차순 정렬이므로 start를 늘리면 값은 증가하고 end를 줄이면 값은 감소한다.
나름 합리적인 방법이지만 해당 방식은 모든 경우의 수를 탐색하지 않는다.
단지 현재 상황에서 target값인 M에 근사 하기 위한 최적의 선택을 할 뿐이다.
위의 로직에 의해 두 수의 조합을 탐색했다고 했을 때 혹시 탐색하지 않은 조합에 target값 M과 더 근사한 조합이 있지 않을까? 하는 의문이 생길 수 있다.
결론부터 말하자면 Two Pointer방식을 사용하면 항상 target인 M값과 과 가장 근사한 두 수의 합의 조합을 탐색한다.
예를 들어 위와 같이 원소 a~g를 갖는 배열 n에서 M값과 가장 근사한 두 수의 조합을 찾을 경우 c + e가 가장 M값과 근사한 값이고 정답인 조합이라고 하자. (두 수의 합이 M값과 일치하는 조합은 없다고 한다)
[예제 1]
두 수의 합이 M값과 일치하는 조합(n[start] + n[end] != M)이 없기 때문에 각각의 포인터들은 서로 겹칠 때까지 계속해서 이동하게 되고, 어떤 포인터가 먼저 인지는 알 수 없지만 start 또는 end 포인터는 각각 c 또는 e에 항상 도달하게 된다.
여기서 만약 start가 정답인 c에 먼저 도달했다고 하자.
[예제 2]
이 상황에서 Two Pointer 로직에 의해 혹시라도 start가 d로 이동하는 일은 없을까? c와 e의 조합을 탐색하지 못하는 일은 없을까? 라는 의문이 생길 수 있다.
하지만 위의 상황에서 start 포인터는 적어도 end가 정답인 e에 도달할 때까지 절대 움직이지 않는다.
위의 상황에서 "start 포인트가 움직여야 한다"라고 하자
start 포인트가 움직이는 경우는 두 정수의 합이 M보다 적을 때이다.
위의 상황에서는 start 포인트가 이동하기 위해서는 다음이 성립해야 한다.
c + g < M
c + g = M + x 라고 하자.
그렇다면 위의 부등호에서
c + g < M
→ M + x < M
→ x < 0
즉 x는 음수가 된다.
c + e = M + ∂ 이라고 한다면,
이때 배열 n은 오름차순 이므로
c + e < c + g
→ M + ∂ < M + x
→ ∂ < x < 0 이 성립한다.
그런데 ∂는 조건상 배열 n에서 조합할 수 있는 모든 경우의 M - (n[start] + n[end])보다 항상 작다.
때문에 항상 |∂| < |x| 여야 한다.
앞의 전제에서 이끌어낸 부등식 ∂ < x < 0 에 의해 ∂와 x는 음수이고 절댓값을 씌우면 |∂| > |x| 이 된다.
전제인 "start 포인트가 이동하는 상황" 에서 모순이 발생했기 때문에 이 전제는 부정된다.
따라서 start 포인트는 이동하지 않는다.
이는 end가 e에 도달할 때까지 유효하다.
반대로 end가 먼저 정답인 e에 도달했을 때도 start가 c에 도달할 때까지 end 포인트는 움직이지 않는다.
따라서 Two Pointer 방식은 항상 target값인 M과 근사한 두 수의 조합을 탐색한다.
3. Code
■ threeSumClosest
[threeSumClosest]
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int minDiff = 100000;
for (int i = 0; i < nums.length; i++) { //숫자 하나 선택
int newTarget = target - nums[i]; //target에서 선택한 숫자만큼 뺀 값을 newTarget으로 정의
int start = 0; //start, end point 설정, 선택한 숫자의 인덱스와 겹치면 변경
if (i == start) {
start++;
}
int end = nums.length - 1;
if (i == end) {
end--;
}
while (start != end) { //newTarget에 근접하는 방향으로 start, end를 움직이면서 합을 구함
int sum = nums[start] + nums[end];
if (sum == newTarget) { //숫자의 합이 target과 동일한 경우가 있다면 target을 바로 반환
return target;
}
if (sum < newTarget) {
if (start + 1 == i) {
start += 2;
} else {
start++;
}
}
if (sum >= newTarget) {
if (end - 1 == i) {
end -= 2;
} else {
end--;
}
}
if (Math.abs(sum - newTarget) < Math.abs(minDiff)) { //target과 가장 작은 차이가 나는 값을 갱신
minDiff = sum - newTarget;
}
}
}
return target + minDiff;
}
□ 값 설정
[값 설정]
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums); //[1]
int minDiff = 100000; //[2]
for (int i = 0; i < nums.length; i++) { //[3]
int newTarget = target - nums[i]; //[4]
int start = 0; //[5]
if (i == start) {
start++;
}
int end = nums.length - 1;
if (i == end) {
end--;
}
.
.
.
}
}
return target + minDiff;
}● [1] : 오름차순으로 정렬
● [2] : target과 정수 합의 차의 최솟값이 들어올 변수를 초기화
● [3] : 반복문을 돌며, 인덱스 i에 위치한 숫자를 하나 선택하고 Two Pointer 방식을 이용해 두 정수를 선택한다.
● [4] : 선택한 숫자를 target에서 뺀 값을 새로운 타겟값 newTarget으로 설정한다.
● [5] : start와 end 포인터를 설정. 만약 인덱스 i와 포인터가 겹친다면 한 자리 넘어간다.
□ Two Pointer
[Two Pointer]
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int minDiff = 100000;
for (int i = 0; i < nums.length; i++) {
.
.
.
while (start != end) { //[1]
int sum = nums[start] + nums[end];
if (sum == newTarget) { //[2]
return target;
}
if (sum < newTarget) { //[3]
if (start + 1 == i) {
start += 2;
} else {
start++;
}
}
if (sum >= newTarget) {
if (end - 1 == i) {
end -= 2;
} else {
end--;
}
}
if (Math.abs(sum - newTarget) < Math.abs(minDiff)) { //[4]
minDiff = sum - newTarget;
}
}
}
return target + minDiff; //[5]
}● [1] : 반복문을 돌며 Two Pointer를 사용해서 두 정수를 선택
● [2] : 만약 두 정수의 합이 newTarget과 일치한다면 합이 target값과 일치하는 세 정수가 존재한다는 뜻이기 때문에 바로 target을
반환해준다.
● [3] : Two Pointer 로직에 의해 target값과 두 정수의 합이 근사하도록 두 정수의 조합을 탐색한다.
● [4] : minDiff에 두 정수의 합과 newTarget의 차이의 최솟값이 갱신되도록 설정
● [5] : target값에 세 정수의 합과 target값의 차이의 최솟값인 minDiff를 더해서 반환
■ 전체 코드
[전체 코드]
import java.util.Arrays;
public class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int minDiff = 100000;
for (int i = 0; i < nums.length; i++) { //숫자 하나 선택
int newTarget = target - nums[i]; //target에서 선택한 숫자만큼 뺀 값을 newTarget으로 정의
int start = 0; //start, end point 설정, 선택한 숫자의 인덱스와 겹치면 변경
if (i == start) {
start++;
}
int end = nums.length - 1;
if (i == end) {
end--;
}
while (start != end) { //newTarget에 근접하는 방향으로 start, end를 움직이면서 합을 구함
int sum = nums[start] + nums[end];
if (sum == newTarget) { //숫자의 합이 target과 동일한 경우가 있다면 target을 바로 반환
return target;
}
if (sum < newTarget) {
if (start + 1 == i) {
start += 2;
} else {
start++;
}
}
if (sum >= newTarget) {
if (end - 1 == i) {
end -= 2;
} else {
end--;
}
}
if (Math.abs(sum - newTarget) < Math.abs(minDiff)) { //target과 가장 작은 차이가 나는 값을 갱신
minDiff = sum - newTarget;
}
}
}
return target + minDiff;
}
}
댓글