두 개의 목록 nums1과 nums2가 있다고 가정합니다. 이 두 목록은 각각 실행 길이로 인코딩된 형식으로 벡터를 나타냅니다. 예를 들어 벡터 [1, 1, 1, 2, 2, 2, 2]는 [3, 1, 4, 2]로 표시됩니다. (3개의 1과 4개의 2가 있기 때문에). 따라서 우리는 이 두 벡터의 내적을 찾아야 합니다. (내적은 두 벡터에 있는 항목의 요소별 곱셈의 합입니다.)
따라서 입력이 nums1 =[2, 7, 5, 3] nums2 =[3, 5, 4, 2]와 같으면 출력은 109가 됩니다. 벡터는 [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.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- ans :=0
- nums1과 nums2가 모두 비어 있지 않은 동안 do
- val1 :=nums1의 마지막 요소 및 마지막 항목 삭제
- count1 :=nums1의 마지막 요소 및 마지막 항목 삭제
- val2 :=nums2의 마지막 요소 및 마지막 항목 삭제
- count2 :=nums2의 마지막 요소 및 마지막 항목 삭제
- ans :=ans + (val1 * val2) * (count2와 count1의 최소값)
- count2> count1이면
- 삽입 |count2 - count1| nums2의 끝에
- nums2 끝에 val2 삽입
- 그렇지 않으면 count1> count2일 때
- 삽입 |count2 - count1| nums1 끝에
- nums1 끝에 val1 삽입
- 반환
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
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