목록을 연속적으로 증가하는 하위 목록으로 분할할 수 있는지 여부를 Python에서 확인하는 프로그램

nums라고 하는 숫자 목록이 있고 비감소 순서로 정렬되어 있다고 가정하면 각 하위 시퀀스의 길이가 최소 3이고 연속적으로 증가하도록 여러 하위 시퀀스로 분할할 수 있는지 확인해야 합니다.

따라서 입력이 nums =[2, 3, 4, 4, 5, 6, 7]과 같으면 목록을 [2, 3, 4] 및 [4, 5, 6, 7].

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

• counts :=num의 요소와 해당 개수를 포함하는 지도
• starts :=새 목록
• ends :=새 목록
• 정렬된 순서로 개수 항목의 각 x에 대해 다음을 수행합니다.
  • count[x]> count[x - 1]이면
    • l :=크기 목록(count[x] - count[x - 1]) 및 x로 채우기
    • 시작 부분에 l 삽입
  • count[x]> count[x + 1]이면
    • l :=크기 목록(count[x] - count[x + 1]) 및 x로 채우기
    • 시작 부분에 l 삽입
• 모든 (start, end) 쌍이 (start + 2 <=end)를 만족하면 true를 반환하고, 그렇지 않으면 false를 반환

예제(파이썬)

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

from collections import Counter
class Solution:
   def solve(self, nums):
      count = Counter(nums)
      starts = []
      ends = []
      for x in sorted(count):
         if count[x] > count[x - 1]:
            starts.extend([x] * (count[x] - count[x - 1]))
         if count[x] > count[x + 1]:
            ends.extend([x] * (count[x] - count[x + 1]))
      return all(s + 2 <= e for s, e in zip(starts, ends))
ob = Solution()
nums = [2, 3, 4, 4, 5, 6, 7]
print(ob.solve(nums))

입력

[6, 7, 5, 10, 13], 2

출력

True