<aside> 💬 lv0, 탐색, 투 포인터

가장 가까운 합 찾기

문제 설명

정렬된 정수 배열과 타겟 값이 주어집니다. 배열 내의 두 요소를 선택하여 그 합이 타겟 값에 가장 가까워지도록 하는 두 요소의 합을 찾는 코드를 작성해주세요. 두 요소의 합이 타겟 값과 같을 수도, 또는 타겟 값보다 클 수도 있습니다.

제한 사항

• 배열은 오름차순으로 정렬되어 있습니다.
• 배열의 길이는 2 이상 100 이하입니다.
• 배열의 요소와 타겟 값은 정수입니다.

입출력 예

입출력 설명

첫 번째 예시에서 배열 [1, 2, 3, 4, 5] 내에서 합이 타겟 값 10에 가장 가까운 조합은 4와 5의 합인 9입니다. 두 번째 예시에서는 2와 8의 합인 10이 타겟 값 11에 가장 가깝습니다.

</aside>

😺 풀이 1. 포인터, abs

def solution(data): **#1 함수 정의**
    nums, target = data **#2 데이터 분리**
    closest_sum = float("inf") **#3 가장 가까운 합 초기화**
    left, right = 0, len(nums) - 1 **#4 포인터 초기화**

    while left < right: **#5 탐색 조건 정의**
        current_sum = nums[left] + nums[right] **#6 현재 합 정의**
        
        **#7 가장 가까운 합 갱신**
        if abs(target - current_sum) < abs(target - closest_sum):
            closest_sum = current_sum

        **#8 포인터 이동**
        if current_sum < target:
            left += 1
        else:
            right -= 1

    return closest_sum **#9 가장 가까운 합 반환**

단계별 풀이 전략

1. 함수 정의

   코드의 첫 부분에서 solution이라는 함수를 정의합니다. 이 함수는 하나의 인자 data를 받습니다. data는 배열 내 선택한 두 요소의 합이 타겟값과 가까운 배열을 찾기 위한 전체 배열과 타겟값입니다.

2. 데이터 분리

   data에서 전체 배열과 타겟값을 nums 와 target으로 언패킹합니다.

3. 가장 가까운 합 초기화

   가장 가까운 합의 초깃값으로 양의 무한대 float("inf") 를 사용하고 closest_sum 변수에 할당합니다.

4. 포인터 초기화

   여기서 포인터는 배열 nums에서 두 요소를 선택하기 위한 인덱스입니다. 두 요소 중 왼쪽 요소에 사용되는 포인터로 left를 사용하고 오른쪽 요소에 사용되는 포인터로 right를 사용합니다. 그리고 left, right = 0, len(nums) - 1에서 볼 수 있듯이 각 포인터에는 배열의 초깃값으로 양쪽 끝에 해당하는 인덱스값을 할당합니다. 그러므로 left에는 왼쪽 끝 인덱스인 0을, right에는 오른쪽 끝 인덱스인 ‘배열 nums의 길이 len(nums) -1’을 할당합니다.

5. 탐색 조건 정의

   여기서 탐색은 왼쪽 포인터 left가 오른쪽 포인터 right보다 값이 커질 때, 탐색이 의미가 없어져 탐색이 종료됩니다. 그러므로 탐색 조건으로는 왼쪽 포인터 left가 오른쪽 포인터 right보다 작으면 while 문이 반복되는 걸로 하고 탐색을 진행합니다.

6. 현재 합 정의

   먼저 현재 반복문에서 타겟값과의 거리를 구할 현재 합을 정의해야 합니다. 현재 합은 nums[left] + nums[right]로 left, right 포인터로 구한 배열 내 두 요소를 더한 값으로 정의됩니다.

7. 가장 가까운 합 갱신

   두 요소의 합이 타겟값 target에 얼마나 가까운지는 타겟값과 두 요소의 합의 거리가 얼마나 짧냐로 결정됩니다. 그러므로 기존 가장 가까운 합 closest_sum이 갖는 타겟값과의 거리는 abs(target - closest_sum)이 되고, 현재 합 current_sum이 갖는 거리는 abs(target - current_sum)이 됩니다. 여기서 abs 함수는 값을 절댓값으로 만들어 주는 함수로 양수 값만 갖는 거리를 표현하기 위해 사용합니다. 그리고 만일 if abs(target - current_sum) < abs(target - closest_sum):와 같이 현재 합이 타겟값에 더 가까운 합이 된다면, closest_sum에 current_sum을 할당하여 가장 가까운 합을 갱신합니다.

8. 포인터 이동

   새로운 조합을 구하기 위해 분기를 두어 포인터를 움직입니다. 만일 if current_sum < target:과같이 현재 합이 타겟값보다 작다면, left += 1로 포인터 left를 오른쪽으로 1만큼 이동합니다. 만일 else:로 현재의 합이 타겟값 이상이라면, right -= 1로 포인터 right을 왼쪽으로 1만큼 이동합니다.

9. 가장 가까운 합 반환

   while 문이 끝나면서 최종으로 갱신된 가장 가까운 합 closest_sum을 반환합니다.

알아둬야 할 개념

abs 함수

• 기본 형태: abs(정수 또는 실수)

• 개념: abs 함수는 음수를 양수의 형태인 절대적인 값으로 바꿔줍니다.

  a = -5
  abs(a) # 5
  

풀이 2. 이중 for 문

def solution(data): **#1 함수 정의**
    nums, target = data **#2 데이터 분리**
    closest_sum = float("inf") **#3 가장 가까운 합 초기화**
    
    for left in range(0, len(nums) - 1): **#4 left 포인터 정의**
        for right in range(left + 1, len(nums)): **#5 right 포인터 정의**
            if abs((nums[left] + nums[right]) - target) < abs(closest_sum - target): **#6 가장 가까운 합의 갱신 조건 정의**
                closest_sum = nums[left] + nums[right] **#7 가장 가까운 합 갱신**
    return closest_sum **#8 가장 가까운 합 반환**