숫자로 이루어진 리스트 nums가 주어졌을 때, i < j를 만족하는 쌍 (i, j) 중에서 nums[i] + nums[j] + (i - j) 값이 최대가 되는 경우를 찾아야 합니다.
예를 들어 입력이 nums = [6, 6, 2, 2, 2, 8]이라면 결과는 11입니다. 인덱스 0과 1에 있는 두 개의 6을 선택하면 점수가 6 + 6 + (0 - 1) = 11이 되기 때문입니다.
문제 해결 접근 방식
가능한 모든 쌍을 일일이 확인하는 브루트 포스 방식은 O(n²)의 시간이 걸려 비효율적입니다. 대신 식을 다음과 같이 변형하면 한 번의 순회, 즉 O(n) 시간에 문제를 해결할 수 있습니다.
nums[i] + nums[j] + (i - j) = (nums[i] + i) + (nums[j] - j)
즉, 왼쪽 요소에서는 (값 + 인덱스)를, 오른쪽 요소에서는 (값 - 인덱스)를 최대화하면 됩니다. 알고리즘의 단계는 다음과 같습니다.
large := nums[0]
maxi := 0
i를 1부터 nums의 길이까지 반복합니다.
large := large - 1 (인덱스 간격이 벌어질수록 (i - j) 항이 작아지는 것을 반영)
maxi := max(large + nums[i], maxi)
large := max(large, nums[i])
maxi를 반환합니다.
여기서 변수 large는 지금까지 확인한 인덱스 중 nums[k] + k가 가장 컸던 값을 현재 위치 기준으로 보정한 값입니다. 매 반복마다 1씩 감소시킴으로써 두 인덱스의 거리가 멀어질 때 발생하는 (i - j) 감소분을 자연스럽게 처리할 수 있습니다.
아래 구현을 통해 더 자세히 이해해 보겠습니다.
예제 코드
class Solution: def solve(self, nums): large = nums[0] maxi = 0 for i in range(1, len(nums)): large -= 1 maxi = max(large + nums[i], maxi) large = max(large, nums[i]) return maxi ob = Solution() nums = [6, 6, 2, 2, 2, 8] print(ob.solve(nums))
입력
[6, 6, 2, 2, 2, 8]
출력
11
복잡도 분석
시간 복잡도: O(n) — 리스트를 한 번만 순회합니다.
공간 복잡도: O(1) — 추가 변수 두 개만 사용합니다.