파이썬으로 인접하지 않은 두 요소의 최소 합 쌍 찾는 방법

숫자 리스트가 주어졌을 때, 인덱스 i와 j(단, i < j이고 j - i > 1)를 만족하는 모든 쌍 중에서 합이 가장 작은 값을 구하는 문제를 살펴보겠습니다. 여기서 j - i > 1 조건은 서로 인접한 두 요소는 선택할 수 없다는 의미입니다.

예를 들어 입력이 nums = [3, 4, 2, 2, 4]라면 출력은 5가 됩니다. 값 3과 2를 선택하면 합이 5이기 때문입니다. 반면 마지막에 있는 2와 2는 서로 인접해 있어서 j - i > 1 제약 조건을 위반하므로 선택할 수 없습니다.

문제 해결 접근 방법

이 문제는 브루트 포스로 모든 쌍을 확인하는 O(n²) 방식 대신, 선형 시간 O(n)에 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• 현재 위치보다 최소 2칸 이상 앞선 인덱스들 중에서 가장 작은 값을 계속 추적합니다(min_seen).
• 각 인덱스 i에서 min_seen + nums[i]를 계산하여 지금까지의 최소 합(ans)과 비교합니다.
• 인덱스 i - 1의 값은 다음 반복부터 유효한 후보가 되므로, min_seen을 갱신할 때 활용합니다.

알고리즘 단계

• n := 리스트 nums의 크기
• min_seen := nums[0]
• ans := 무한대(inf)
• i를 2부터 n-1까지 반복:
  • ans := ans와 (min_seen + nums[i]) 중 최솟값
  • min_seen := min_seen과 nums[i - 1] 중 최솟값
• ans 반환

구현 예제

아래 파이썬 코드를 통해 더 잘 이해할 수 있습니다.

def solve(nums):
    n = len(nums)
    min_seen = nums[0]

    ans = float("inf")

    for i in range(2, n):
        ans = min(ans, min_seen + nums[i])

        min_seen = min(min_seen, nums[i - 1])
    return ans

nums = [3, 4, 2, 2, 4]
print(solve(nums))

입력

[3, 4, 2, 2, 4]

출력

5

복잡도 분석

이 알고리즘은 리스트를 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가 메모리는 상수 개의 변수만 사용하므로 공간 복잡도는 O(1)입니다. 모든 가능한 쌍을 검사하는 O(n²) 완전 탐색보다 훨씬 효율적입니다.