두 개의 배열 nums1과 nums2가 주어졌다고 가정해 보겠습니다. 여기서 유효한 경로(valid path)는 다음과 같이 정의됩니다.
- nums1 또는 nums2 중 하나를 선택하여 인덱스 0부터 탐색을 시작합니다.
- 선택한 배열을 왼쪽에서 오른쪽 방향으로 순회합니다.
순회 도중 현재 값이 두 배열 모두에 존재하는 값이라면, 그 지점에서 다른 배열로 경로를 전환할 수 있습니다. 이때 점수(score)는 유효한 경로에 포함된 고유한 값들의 합으로 정의되며, 우리는 가능한 모든 유효한 경로 중에서 얻을 수 있는 최대 점수를 구해야 합니다. 만약 답이 너무 크다면 결과를 10^9+7로 나눈 나머지를 반환합니다.
예를 들어, 입력이 nums1 = [3,5,6,9,11], nums2 = [5,7,9,10]이라면 출력은 35가 됩니다. 그 이유는 다음과 같습니다.
- nums1에서 시작하는 유효한 경로: [3,5,6,9,11], [3,5,6,9,10], [3,5,7,9,10], [3,5,7,9,11]
- nums2에서 시작하는 유효한 경로: [5,7,9,10], [5,6,9,11], [5,6,9,10], [5,7,9,11]
이 중 최대 점수를 가지는 경로는 [3,5,7,9,11]이며, 그 합계는 35입니다.
문제 해결 접근 방법
이 문제는 투 포인터(two pointer) 기법을 활용하면 효율적으로 해결할 수 있습니다. 두 배열을 동시에 순회하면서 작은 쪽 값을 각각의 누적합에 더해 가다가, 두 배열에 공통으로 존재하는 값을 만나는 시점에 어느 쪽 경로의 누적합이 더 큰지 비교하여 더 큰 값을 선택하는 방식입니다. 단계별 과정은 다음과 같습니다.
- M := nums1의 크기, N := nums2의 크기로 설정합니다.
- sum1 := 0, sum2 := 0으로 초기화합니다.
- i := 0, j := 0으로 초기화합니다.
- res := 0으로 초기화합니다.
- i < M이고 j < N인 동안 다음을 반복합니다.
- nums1[i] < nums2[j]이면 sum1에 nums1[i]를 더하고 i를 1 증가시킵니다.
- nums1[i] > nums2[j]이면 sum2에 nums2[j]를 더하고 j를 1 증가시킵니다.
- 그 외(두 값이 같은 경우)에는 res에 max(sum1, sum2)와 공통 값 nums1[i]를 더하고, i와 j를 각각 1 증가시킨 뒤 sum1과 sum2를 0으로 초기화합니다.
- i < M인 동안 sum1에 nums1[i]를 더하고 i를 1씩 증가시킵니다.
- j < N인 동안 sum2에 nums2[j]를 더하고 j를 1씩 증가시킵니다.
- (res + max(sum1, sum2)) mod 10^9+7을 반환합니다.
이 알고리즘은 각 배열을 한 번씩만 순회하므로 시간 복잡도는 O(M+N)이며, 추가 배열 없이 상수 공간만 사용하기 때문에 매우 효율적입니다.
예제 코드
아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.
def solve(nums1, nums2):
M, N = len(nums1), len(nums2)
sum1, sum2 = 0, 0
i, j = 0, 0
res = 0
while i < M and j < N:
if nums1[i] < nums2[j]:
sum1 += nums1[i]
i += 1
elif nums1[i] > nums2[j]:
sum2 += nums2[j]
j += 1
else:
res += max(sum1, sum2) + nums1[i]
i += 1
j += 1
sum1 = 0
sum2 = 0
while i < M:
sum1 += nums1[i]
i += 1
while j < N:
sum2 += nums2[j]
j += 1
return (res + max(sum1, sum2)) % 1000000007
nums1 = [3,5,6,9,11]
nums2 = [5,7,9,10]
print(solve(nums1, nums2))입력
[3,5,6,9,11], [5,7,9,10]
출력
35