Computer >> 컴퓨터 >  >> 프로그램 작성 >> Python

Python에서 하위 목록 합계 연산으로 하나의 목록을 다른 목록과 동일하게 변환하는 프로그램

<시간/>

두 개의 목록 l1과 l2가 있다고 가정하고 이 작업을 반복적으로 적용하여 목록을 동일하게 만들어야 합니다. - 하위 목록을 선택하고 전체 하위 목록을 합으로 바꿉니다. 마지막으로 위의 작업을 적용한 후 가능한 가장 긴 결과 목록의 크기를 반환합니다. 해결책이 없으면 -1을 반환합니다.

따라서 입력이 l1 =[1, 4, 7, 1, 2, 10] l2 =[5, 6, 1, 3, 10]인 경우 출력은 4가 됩니다. 마치 이 작업을 다음과 같이 수행하는 것처럼 다음 -

  • l1의 하위 목록 [1, 4]를 가져오면 [5, 7, 1, 2, 10]이 됩니다.
  • l1의 하위 목록 [1, 2]를 가져오면 [5, 7, 3, 10]이 됩니다.
  • l2의 하위 목록 [6, 1]을 가져오면 [5, 7, 3, 10]이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

  • i :=l1 - 1의 크기, j :=l2 - 1의 크기, res :=0
  • i>=0이고 j>=0일 때 수행
    • l1[i]가 l2[j]와 같으면
      • res :=res + 1, i :=i - 1, j :=j - 1
    • 그렇지 않으면 l1[i]
    • i> 0이 0이 아니면
      • l1[i - 1] :=l1[i - 1] + l1[i]
    • 나는 :=나는 - 1
  • 그렇지 않으면 l1[i]> l2[j]일 때
    • j> 0이면
      • l2[j - 1] :=l2[j - 1] + l2[j]
    • j :=j - 1
  • i가 -1과 같고 j가 -1과 같으면 res를 반환하고 그렇지 않으면 -1을 반환합니다.
  • 이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

    class Solution:
       def solve(self, l1, l2):
          i, j, res = len(l1) - 1, len(l2) - 1, 0
          while i >= 0 and j >= 0:
             if l1[i] == l2[j]:
                res, i, j = res + 1, i - 1, j - 1
             elif l1[i] < l2[j]:
                if i > 0:
                   l1[i - 1] += l1[i]
                i -= 1
             elif l1[i] > l2[j]:
                if j > 0:
                   l2[j - 1] += l2[j]
                j -= 1
             return res if i == -1 and j == -1 else -1
    ob = Solution()
    l1 = [1, 4, 7, 1, 2, 10]
    l2 = [5, 6, 1, 3, 10] print(ob.solve(l1, l2))

    입력

    [1, 4, 7, 1, 2, 10], [5, 6, 1, 3, 10]

    출력

    4