Python의 이진 문자열에서 10 또는 01을 제거하여 얻을 수 있는 최대 점수를 찾는 프로그램

이진 문자열 s와 두 개의 값 zero_one과 one_zero가 있다고 가정합니다. 이제 부분 문자열 "01"을 삭제하고 zero_one 포인트를 받을 수 있는 작업을 고려해 보겠습니다. 또는 하위 문자열 "10"을 제거하고 one_zero 포인트를 받을 수 있습니다. 우리는 여러 작업 후에 얻을 수 있는 최대 점수를 찾아야 합니다.

따라서 입력이 s ="10100101" zero_one =3 one_zero =2와 같으면 출력은 11이 됩니다. "01"을 세 번 제거하여 3*3 =9 포인트를 얻을 수 있기 때문입니다. 그러면 나머지 문자열은 10입니다. 이것을 제거하면 또 다른 2점을 얻을 수 있으므로 총점이 11이 됩니다.

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

• A :=입력 문자열로 주어진 비트 목록

• zero_one

  • zero_one 및 one_zero 교환

  • 범위 0에서 A 크기까지의 i에 대해

    • A[i] :=A[i] XOR 1

• 답변 :=0

• 스택 :=새 스택

• A의 각 x에 대해 수행

  • 스택이 비어 있지 않고 스택 맨 위 요소

    • 스택에서 팝

    • ans :=ans + zero_one

  • 그렇지 않으면

    • x를 스택에 푸시

• ans :=ans + one_zero * 스택에서 0이 발생하고 스택에서 1이 발생하는 최소값

• 반환

예제(파이썬)

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

class 솔루션:def solve(self, S, zero_one, one_zero):A =list(map(int, S)) if zero_one  
입력
 
"10100101", 3, 2
 
출력
 
11