파이썬으로 두 숫자 쌍의 합 차이가 최소가 되도록 두 쌍을 찾는 프로그램

숫자 리스트 nums가 주어졌을 때, 이 중에서 두 개의 숫자 쌍을 선택하여 두 쌍의 합 사이의 절대 차이가 최소가 되도록 만드는 프로그램을 작성하는 문제입니다.

예를 들어 입력이 nums = [3, 4, 5, 10, 7]이라면 출력은 1이 됩니다. (3 + 7) - (4 + 5) = 1이 되는 두 쌍을 선택할 수 있고, 이보다 작은 차이를 만들 수 없기 때문입니다.

문제 해결 접근 방법

이 문제는 다음 단계를 따라 해결할 수 있습니다.

거리 정보를 저장할 새로운 리스트 distances를 생성합니다.
i를 0부터 nums의 크기 - 2까지 반복합니다.
- j를 i + 1부터 nums의 크기 - 1까지 반복하며, distances 리스트 끝에 [|nums[i] - nums[j]|, i, j] 형태의 값을 추가합니다.
distances 리스트를 정렬합니다.
정답 변수 ans를 충분히 큰 값(1e9)으로 초기화합니다.
i를 0부터 distances의 크기 - 2까지 반복합니다.
- [dist, i1, i2] := distances[i]로 설정합니다.
- j := i + 1로 설정하고, [dist2, i3, i4] := distances[j]를 가져옵니다.
- j가 distances 범위 안에 있으면서 네 개의 인덱스(i1, i2, i3, i4)가 모두 서로 다르지 않은 동안 j를 증가시키며 다음 거리를 확인합니다.
- 네 개의 인덱스가 모두 고유하다면, ans와 (dist2 - dist) 중 더 작은 값을 ans에 저장합니다.
최종적으로 ans를 반환합니다.

즉, 모든 숫자 쌍의 절대 차이를 미리 계산해 정렬한 뒤, 서로 겹치지 않는 인덱스를 가진 인접한 두 거리의 차이 중 최솟값을 찾는 방식입니다.

예제 코드

아래 구현을 통해 더 자세히 이해해 보겠습니다.

class Solution:
   def solve(self, nums):
      distances = []
      for i in range(len(nums) - 1):
         for j in range(i + 1, len(nums)):
            distances.append((abs(nums[i] - nums[j]), i, j))
      distances.sort()
      ans = 1e9
      for i in range(len(distances) - 1):
         dist, i1, i2 = distances[i]
         j = i + 1
         dist2, i3, i4 = distances[j]
         while j < len(distances) and len({i1, i2, i3, i4}) != 4:
            dist2, i3, i4 = distances[j]
            j += 1
         if len({i1, i2, i3, i4}) == 4:
            ans = min(ans, dist2 - dist)
      return ans

ob = Solution()
nums = [3, 4, 5, 10, 7]
print(ob.solve(nums))

입력

[3, 4, 5, 10, 7]