솔루션: 부분 문자열 제거의 최대 점수 (ver. 1)

이것은 일련의 Leetcode 솔루션 설명( )의 일부입니다. 이 솔루션이 마음에 드셨거나 유용하셨다면 이 게시물에 좋아요를 누르거나 추천my solution post on Leetcode's forums 해주세요.


참고: 이것은 이 문제에 대한 솔루션 게시물의 첫 번째 버전입니다. 컨셉은 멋지지만 .

Leetcode 문제 #1717(중간): 부분 문자열 제거의 최대 점수

설명:

문자열s과 두 개의 정수x 및 y가 제공됩니다. 두 가지 유형의 작업을 여러 번 수행할 수 있습니다.

부분 문자열"ab"을 제거하고 x점을 얻습니다.

예를 들어 "ab"에서 "cabxbae"를 제거하면 "cxbae" 가 됩니다.

부분 문자열"ba"을 제거하고 점수y를 얻습니다.

예를 들어 "ba"에서 "cabxbae"를 제거하면 "cabxe" 가 됩니다.

s 에 위의 연산을 적용한 후 얻을 수 있는 최대 점수를 반환합니다.


예:


예 1:



입력:
s = "cdbcbbbaaabab", x = 4, y = 5

산출:
19

설명:
"cdbcbbbaaaab"에서 밑줄이 그어진 "ba"를 제거합니다. 이제 s = "cdbcbbbaaab"이고 5점이 점수에 추가됩니다. "cdbcbbaaab"에서 밑줄이 그어진 "ab"를 제거합니다. 이제 s = "cdbcbbaa"이고 4점이 추가됩니다. "cdbcbbaa"에 밑줄이 그어진 "ba"를 제거합니다. 이제 s = "cdbcba"이고 5점이 점수에 추가됩니다. "cdbcba"에 밑줄이 그어진 "ba"를 제거합니다.지금, s = "cdbc"및 5점이 점수에 추가됩니다. 총점 = 5 + 4 + 5 + 5 = 19입니다.



예 2:



입력:
s = "aabbaaxybbbaabb", x = 5, y = 4

산출:
20



제약:

1 <= s.length <= 10^5

1 <= x, y <= 10^4

s는 영문 소문자로 구성되어 있습니다.

아이디어:

여기서 문제는 두 가지입니다. 첫 번째 문제는 낮은 값의 작업을 수행하기 전에 높은 값의 작업을 가능한 한 많이 탐욕스럽게 수행해야 한다는 점에서 비교적 쉽습니다. 작업에서 제안하는 대로 입력을 계속해서 연결할 수 있지만 이는 매우 비효율적이므로 대신 실제로 연결을 수행하지 않아도 되는 몇 가지 포인터만 사용할 수 있습니다.

그러나 두 번째 문제는 S를 여러 번 실행해야 한다는 것입니다. 즉, 첫 번째 패스와 두 번째 패스 사이의 포인터 이동을 "기억"하는 수단 없이는 간단한 두 포인터 시스템이 자체적으로 작동하지 않습니다.

즉, 두 번째 작업을 시작하기 전에 첫 번째 작업 세트 이후에 수정된 문자열을 저장하는 방법이 있어야 합니다. 우리는 항상 S의 값을 푸시할 수 있는 새 스택 배열을 만들 수 있지만 이 시점에서 S를 배열로 분할하는 것이 더 효율적입니다. 그러면 S의 개별 값을 제자리에 다시 쓸 수 있습니다.

일단 그렇게 하면 2포인터 시스템을 실행할 수 있습니다. 하나의 포인터(j)는 S의 현재 위치를 추적하고 S의 첫 번째 부분을 스택인 것처럼 취급하고 다른 포인터( i) 해당 스택의 "끝"을 추적합니다.

      S = "abxaabb" = [ "a", "b", "x", "a", "a", "b", "b" ]
pattern = "ab"


                i,j                        // Start i & j at the pattern length
S = [ "a", "b", "x", "a", "a", "b", "b" ]  // Then check the last 2 "stack" entries
       ^*!!*^                              // to see if they match the pattern

       i <-- <-- j                         // If they match, then we move i back 2
S = [ ___, ___, "x", "a", "a", "b", "b" ]  // simulating removal from the "stack"
                                           // Those values will be overwritten later

       i         j                         // At the end of each iteration
S = [ "x", ___, "x", "a", "a", "b", "b" ]  // we shift the next value to the "stack"
       ^----------                         // by overwriting S[i] with S[j]...

        --> i     --> j                    // ...and then we increase the 2 pointers
S = [ "x", ___, ___, "a", "a", "b", "b" ]  // for the start of the next iteration


             --> i     --> j               // No match is found
S = [ "x", "a", ___, ___, "a", "b", "b" ]  // so we just move ahead
            ^----------

                  --> i     --> j          // No match is found
S = [ "x", "a", "a", ___, ___, "b", "b" ]  // so we just move ahead
                 ^----------

                       --> i     --> j
S = [ "x", "a", "a", "b", ___, ___, "b" ]  // A match is found...
                 ^*!*^ ^--------

                 i <-- <--           j
S = [ "x", "a", ___, ___, ___, ___, "b" ]  // ...so we move i back 2


                  --> i               --> j   // Clearly, we must allow j to go one
S = [ "x", "a", "b", ___, ___, ___, ___ ]     // past the end of S to allow for the
            ^*!*^ ^-------------------        // last value of S to complete a match

             --> i <--                    --> j   // Once we're done with this pass
S = [ "x", ___, ___, ___, ___, ___, ___ ]         // anything from i-1 on is garbage
            ^-----------------------------        // and should be removed


S = [ "x" ]                                       // Splice to prepare for pass #2

구현:

패턴을 더 쉽게 비교할 수 있도록 "a"와 "b"를 별도의 변수로 분리할 수 있습니다. 그런 다음 어떤 패턴이 더 가치가 있는지 모르기 때문에 시작하기 전에 필요한 경우 패턴(a, b)과 값 변수(X, Y)를 교체하기 위해 구조 분해 할당을 활용할 수 있습니다.

그런 다음 두 단계를 반복할 수 있습니다. 두 패스 사이에서 S의 원치 않는 끝을 연결하고 두 번째 패스에 대한 패턴 및 값 변수를 교환하기 위해 구조 분해 할당을 사용해야 합니다.

그런 다음 최적의 as를 반환합니다.


자바스크립트 코드:

var maximumGain = function(S, X, Y) {
    S = S.split('')
    let len = S.length, ans = 0, a = "a", b = "b", i, j
    if (Y > X) [a,b,X,Y] = [b,a,Y,X]
    for (let t = 0; t < 2; t++) {
        for (i = j = 2; j <= len; S[i++] = S[j++])
            if (i > 1 && S[i-2] === a && S[i-1] === b)
                ans += X, i -= 2
        len = i - 1, S.splice(len), [a,b,X,Y] = [b,a,Y,X]
    }
    return ans
};