두 개의 리스트 nums1과 nums2가 있다고 가정해 봅시다. 이 두 리스트는 각각 런-렝스 인코딩(Run-Length Encoding, RLE) 형태로 압축된 벡터를 나타냅니다.
예를 들어, 벡터 [1, 1, 1, 2, 2, 2, 2]는 [3, 1, 4, 2]로 표현할 수 있습니다. 값 1이 3개, 값 2가 4개 연속으로 나타나기 때문입니다. 즉, RLE 형식에서 리스트는 [개수, 값, 개수, 값, ...]의 쌍으로 구성됩니다.
우리의 목표는 이렇게 인코딩된 두 벡터의 내적(dot product)을 구하는 것입니다. 내적이란 두 벡터에서 서로 대응하는 원소끼리 곱한 값을 모두 더한 합계를 말합니다.
문제 예시
입력이 다음과 같다고 가정해 보겠습니다.
nums1 = [2, 7, 5, 3]
nums2 = [3, 5, 4, 2]
이 입력은 각각 벡터 [7, 7, 3, 3, 3, 3, 3]과 [5, 5, 5, 2, 2, 2, 2]를 의미합니다. 따라서 내적은 다음과 같이 계산됩니다.
[7, 7, 3, 3, 3, 3, 3] · [5, 5, 5, 2, 2, 2, 2]
= 7×5 + 7×5 + 3×5 + 3×2 + 3×2 + 3×2 + 3×2
= 35 + 35 + 15 + 6 + 6 + 6 + 6
= 109
따라서 출력 결과는 109가 됩니다.
해결 알고리즘
RLE 벡터를 실제 배열로 펼치지 않고도 내적을 효율적으로 계산할 수 있습니다. 각 벡터의 끝에서부터 하나의 (개수, 값) 묶음씩 꺼내어 겹치는 구간만큼 곱해 누적하고, 남은 개수는 다시 해당 벡터에 되돌려 넣는 방식입니다. 단계별로 살펴보면 다음과 같습니다.
- 결과를 저장할 변수
ans를 0으로 초기화합니다. - nums1과 nums2가 모두 비어 있지 않은 동안 다음을 반복합니다.
- nums2의 마지막에서 값(val2)과 개수(count2)를 꺼냅니다.
- nums1의 마지막에서 값(val1)과 개수(count1)를 꺼냅니다.
ans에 (val1 × val2) × min(count1, count2)를 더합니다. 두 구간 중 짧은 쪽 길이만큼만 실제로 겹치기 때문입니다.- count2 > count1이면, 남은 개수 |count2 − count1|과 값 val2를 nums2에 다시 추가합니다.
- count1 > count2이면, 남은 개수 |count1 − count2|과 값 val1을 nums1에 다시 추가합니다.
- 반복이 끝나면
ans를 반환합니다.
구현 코드
위 알고리즘을 파이썬으로 구현하면 다음과 같습니다.
def solve(nums1, nums2):
ans = 0
while nums1 and nums2:
val1 = nums1.pop()
count1 = nums1.pop()
val2 = nums2.pop()
count2 = nums2.pop()
ans += (val1 * val2) * min(count2, count1)
if count2 > count1:
nums2.append(abs(count2 - count1))
nums2.append(val2)
elif count1 > count2:
nums1.append(abs(count2 - count1))
nums1.append(val1)
return ans
nums1 = [2, 7, 5, 3]
nums2 = [3, 5, 4, 2]
print(solve(nums1, nums2))실행 결과
입력
[2, 7, 5, 3], [3, 5, 4, 2]
출력
109
복잡도 분석
이 알고리즘은 벡터를 실제로 확장하지 않고 RLE 묶음 단위로만 처리하기 때문에 매우 효율적입니다. 시간 복잡도는 두 벡터의 RLE 쌍 개수의 합에 비례하여 O(n)이며, 여기서 n은 두 벡터에 포함된 (개수, 값) 쌍의 총 개수입니다. 공간 복잡도 역시 추가 저장 없이 기존 리스트를 재활용하므로 O(1)의 추가 공간만 필요합니다. 벡터의 실제 길이가 수백만 개에 달하더라도 RLE 표현 덕분에 빠르게 내적을 계산할 수 있다는 점이 이 방법의 가장 큰 장점입니다.