Python에서 각 문자가 최대 한 조각으로 나타나는 목록의 각 파티션 크기를 찾는 프로그램

소문자 문자열 s가 있다고 가정하면 각 문자가 최대 한 조각으로 나타나도록 s를 가능한 한 많은 조각으로 나누고 파티션의 크기를 목록으로 찾을 수 있습니다.

따라서 입력이 s ="momoplaykae"와 같으면 문자열이 ["momo", "p", "l", "로 분할되므로 출력은 [4, 1, 1, 4, 1]이 됩니다. ayka", "e"].

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

• count :=s에 있는 문자와 해당 문자를 포함하는 맵

• out :=새 목록, stk :=빈 스택

• 길이 :=0

• s의 각 문자에 대해

  • 개수[문자] :=개수[문자] - 1

  • 길이 :=길이 + 1

  • count[char]가 0과 같지 않거나 stk가 비어 있지 않은 동안 수행

    • count[char]가 0과 같지 않으면

      • stk에 char 푸시

      • 루프에서 나오다

    • stk가 비어 있지 않고 count[stk의 상단]이 0과 같으면

      • stk에서 팝

    • 그렇지 않으면

      • 루프에서 나오다

  • stk가 비어 있고 count[char]가 0과 같으면

    • 출력 후 길이 삽입

    • 길이 :=0

• 반환

예시

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

from collections import Counter
class Solution:
   def solve(self, s):
      count = Counter(s)
      out = []
      stk = []
      length = 0
      for char in s:
         count[char] -= 1
         length += 1
         while count[char] != 0 or stk:
            if count[char] != 0:
               stk.append(char)
               break
            if stk and count[stk[-1]] == 0:
               stk.pop()
            else:
               break
            if not stk and count[char] == 0:
               out += [length]
               length = 0
         return out
ob = Solution()
s = "momoplaykae"
print(ob.solve(s))

입력

"momoplaykae"

출력

[4, 1, 1, 4, 1]