Python에서 정확히 k개의 다른 단어를 포함하는 하위 목록의 수를 찾는 프로그램

<시간/>

단어 목록과 다른 값 k가 있다고 가정합니다. 정확히 k개의 다른 단어가 있도록 주어진 단어에서 하위 목록의 수를 찾아야 합니다.

따라서 입력이 단어 =["Kolkata", "Delhi", "Delhi", "Kolkata"] k =2와 같은 경우 다음 하위 목록에 2개의 고유 단어가 있으므로 출력은 5가 됩니다. ["Kolkata" , "델리"], ["델리", "콜카타"],["콜카타","델리","델리"], ["델리","델리","콜카타"], ["콜카타"," Delhi","Delhi","Kolkata"]가 있지만 ["Delhi","Delhi"]는 고유한 단어가 하나뿐이므로 그렇지 않습니다.

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

work() 함수를 정의합니다. 이것은 단어가 필요합니다. k
n :=단어 크기
k가 0과 같으면
- 0을 반환
cnt :=새 지도
ans :=0
l :=0
0~n 범위의 r에 대해
- 단어:=단어[r]
- 단어가 cnt에 없으면
  - cnt[단어] :=0
- cnt[단어] :=cnt[단어] + 1
- cnt의 크기> k, do
  - cnt[단어[l]] :=cnt[단어[l]] - 1
  - cnt[단어[l]]가 0과 같으면
    - cnt에서 단어[l] 제거
  - l :=l + 1
- ans :=ans + r - l + 1
반환

기본 메소드에서 return (work(words, k) - work(words, k - 1))

예제(파이썬)

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

class Solution:
   def solve(self, words, k):
      return self.work(words, k) - self.work(words, k - 1)
   def work(self, words, k):
      n = len(words)
      if k == 0:
         return 0
      cnt = dict()
      ans = 0
      l = 0
      for r in range(n):
         word = words[r]
         if word not in cnt:
            cnt[word] = 0
         cnt[word] += 1
         while len(cnt) > k:
            cnt[words[l]] -= 1
            if cnt[words[l]] == 0:
               del cnt[words[l]]
            l += 1
         ans += r - l + 1
      return ans
ob = Solution()
words = ["Kolkata", "Delhi", "Delhi", "Kolkata"]
k = 2
print(ob.solve(words, k))

입력

["Kolkata", "Delhi", "Delhi", "Kolkata"], 2