문제: https://leetcode.com/problems/3sum-closest
요청한 내용
다음은 내가 풀이한 알고리즘 문제와 코드야.
난 알고리즘 문제를 풀 때, 주석을 영어로 작성하는 연습을 하려 해.
내가 작성한 코드를 읽고 적혀있는 주석을 영어로 변경하기 위해.
1. 영어로 알고리즘 문제 풀이에 앞서 적절한 의사 코드를 작성하기 위한 계획을 소개
2. 1.에서 소개한 계획과 내가 작성한 코드에 적힌 의사 코드를 비교, 및 피드백.
3. 내가 작성한 주석을 영어로 작성한다면 어떨지, 소개
4. 3. 번에서 소개한 번역된 주석과, 2.에서 피드백해 준 내용을 통해 업그레이드한 의사 코드 및 주석을 소개
위와 같은 작업을 진행해 줘
class Solution {
public:
// 1. target과 가장 가까운 값을 찾음 with lower_bound; (X)
// 오답: target과 일치하는 element를 포함하지 않은 조합이 정답인 경우, exception: [-1,2, 0, 1,-4], target = 1;
// 2. 범위 [left, right]: [0, n-1]를 two-pointer로 순환하며, elements of [left, right] equal 3까지 반복 (X)
// idea: middle 값은 반드시 left <= middle <= right 임을 만족.
// 즉, (nums[left] + nums[middle] + nums[right]) >= (2 * nums[left] + nums[right])
// 구현:
/*
while(right - left + 1 == 3) {
if (2 * nums[left] + nums[right] >= target) right--;
else left++;
}
*/
// 오답: target과 가깝게 만들 수있는 element의 조합이 반드시 연속적이지 않음. ex) [ -4 -1 0 1 2 ], target = 1
// 3. O(n^2), two_pointer를 사용해, 모든 원소 조합을 살펴본뒤, 가장 target과 가까운 값 return
template<typename T>
void print_arr(const T& vec) {
cout << "[ ";
for (int n : vec) {
cout << n << " ";
}
cout << "]\\n";
}
/*
3 <= nums.length <= 500
-1000 <= nums[i] <= 1000
-104 <= target <= 104
*/
int threeSumClosest(vector<int>& nums, int target) {
size_t n = nums.size();
sort(nums.begin(), nums.end());
// DEBUG
print_arr(nums);
// two_pointer 알고리즘 실행 이전에 빠르게 판단할 수 있는 경우들
// 1. n == 3 인경우. 값들의 비교여부와 상관없이 nums의 모든 값들을 더해 return nums[0] + nums[1] + nums[2];
// 2. sum of range in [0, 2] greater than or equal to target; return nums[0] + nums[1] + nums[2];
// 3. sum of range in [n-3, n-2, n-1] less than or eqaul to target; return nums[n-3] + nums[n-2] + nums[n-1];
if (n == 3) return nums[0] + nums[1] + nums[2];
else if (nums[0] + nums[1] + nums[2] >= target) return nums[0] + nums[1] + nums[2];
else if (nums[n-3] + nums[n-2] + nums[n-1] <= target) return nums[n-3] + nums[n-2] + nums[n-1];
int max_diff = 1e9+9;
int answer = 1e9+9;
// if minDiff return zero, then break the loop and return the value;
auto minDiff = [&answer, &max_diff, target](int sum) -> int {
int diff = abs(target - sum);
if (max_diff > diff) {
max_diff = diff;
answer = sum;
}
return diff;
};
for (int i = 0; i < n - 2; i++) {
int cur = nums[i];
int left = i + 1;
int right = n - 1;
while (left < right) {
int sum = cur + nums[left] + nums[right];
if (minDiff(sum) == 0) {
return target;
}
if (sum < target) left++;
// sum > target
else right--;
}
}
return answer;
}
};
알고리즘 문제풀이에서 의사코드를 작성할 때는 보통 다음 단계를 따릅니다:
Step 0. Define Input & Output clearly
→ What are the inputs, constraints, and expected output?
Step 1. Edge Case Handling
→ Handle trivial or boundary cases directly (e.g., array size too small, all zeros, etc.).
Step 2. Preprocessing
→ Sort the array or prepare data structures needed for efficient computation.
Step 3. Main Algorithm Structure
→ Usually a loop or recursive framework that defines the “shape” of the algorithm (e.g., fixing one element, then applying two-pointer search).
Step 4. Update Rule
→ How to compare candidate solutions and update the best answer (often involves keeping track of minimum difference).
Step 5. Termination Condition
→ When do we break early? (e.g., exact match found)
Step 6. Return Final Answer
👉 이렇게 적으면, 사람이 읽었을 때 구현 전에도 로직이 명확하게 보이는 형태가 됩니다.
당신의 코드 주석은 좋은 출발이지만, 몇 가지 개선 포인트가 있어요: