길이가 같은 두 개의 숫자 리스트 A와 B가 있다고 가정해 봅시다. 우리가 구해야 하는 것은 모든 0 ≤ i < j < n에 대해 다음 식의 최댓값입니다.
|a[i] − a[j]| + |b[i] − b[j]| + |i − j|
예를 들어 입력이 A = [2, 4, 10, 6], B = [3, 4, 7, 5]라면 출력은 14가 됩니다. i = 0, j = 2일 때 |2 − 10| + |3 − 7| + |1 − 3| = 8 + 4 + 2 = 14이기 때문입니다.
접근 방법
절댓값이 포함된 식을 그대로 모든 쌍 (i, j)에 대해 계산하면 O(n²)의 시간이 걸립니다. 하지만 절댓값을 전개하면 각 항은 부호에 따라 ±a[i], ±b[i], ±i 형태로 표현됩니다. 따라서 네 가지 부호 조합 (s, t) ∈ {(−1, −1), (−1, 1), (1, −1), (1, 1)}마다 s·a[i] + t·b[i] + i 값을 한 번의 순회로 계산하여 그 최댓값과 최솟값의 차이를 구하면, 전체 문제를 O(n) 시간에 해결할 수 있습니다.
이를 해결하기 위해 다음 단계를 따릅니다 −
- ans := 0
- n := a의 크기
- [(-1, -1), (-1, 1), (1, -1), (1, 1)]의 각 쌍 (s, t)에 대해 다음을 수행합니다.
- cur_min := 무한대(infinity)
- cur_max := 음의 무한대(-infinity)
- i를 0부터 n-1까지 반복하며 다음을 수행합니다.
- tmp := s * a[i] + t * b[i] + i
- cur_min := cur_min과 tmp 중 최솟값
- cur_max := cur_max와 tmp 중 최댓값
- ans := ans와 (cur_max − cur_min) 중 최댓값
- ans 반환
더 나은 이해를 돕기 위해 다음 구현을 살펴보겠습니다 −
예제
class Solution:
def solve(self, a, b):
ans = 0
n = len(a)
for s, t in [(-1, -1), (-1, 1), (1, -1), (1, 1)]:
cur_min = float("inf")
cur_max = float("-inf")
for i in range(n):
tmp = s * a[i] + t * b[i] + i
cur_min = min(cur_min, tmp)
cur_max = max(cur_max, tmp)
ans = max(ans, cur_max - cur_min)
return ans
ob = Solution()
A = [2, 4, 10, 6]
B = [3, 4, 7, 5]
print(ob.solve(A, B))
입력
[2, 4, 10, 6],[3, 4, 7, 5]
출력
14