[LeetCode] 1717. Maximum Score From Removing Substrings

https://leetcode.com/problems/maximum-score-from-removing-substrings/

leetcode - Maximum Score From Removing Substrings

문제 유형 : 그리디, 스택, 슬라이딩 윈도우
문제 난이도 : Medium
 

문제

You are given a string s and two integers x and y. You can perform two types of operations any number of times.

• Remove substring "ab" and gain x points.
  • For example, when removing "ab" from "cabxbae" it becomes "cxbae".
• Remove substring "ba" and gain y points.
  • For example, when removing "ba" from "cabxbae" it becomes "cabxe".

Return the maximum points you can gain after applying the above operations on s.
 
문자열 s와 두 정수 x, y를 받는다. 두 가지 연산을 수행할 수 있다.
 
문자열에서 "ab"를 지우고 x점 얻기
문자열에서 "ba"를 지우고 y점 얻기
 
s에서 연산을 하여 얻을 수 있는 최대 점수를 구하시오.
 

풀이

우리는 되도록이면 x, y중 더 점수가 높은 것을 먼저 얻는게 우선임을 알고 있다.
아래 예시를 보자.
s = "cdbcbbaaabab", x = 4, y = 5 에서 s를 a또는 b, 그리고 아닌 것으로 나눠보자.
 
cd b c bbaaabab.
y가 더 높으므로, ba부터 없애주면 이득이겠다.
cd b c bbaaabab
 
여기서, 문자열 "bbaa"는 안쪽의 ba부터 없애면 또 ba가 되므로, 없앨 수 있다.
3개를 지워서 15점을 얻었다.
그 뒤, ab의 쌍들을 지어 모두 없애주면 된다. 빨간색 표시를 없앤 부분을 보자.
cd b c ab
 
ab쌍은 하나 남는다.
 
여기서, 우리는 다음과 같은 사실들을 알아낼 수 있다:

1. 오로지 a 또는 b로만 주어진 부분문자열에서만 점수를 얻는다는 것.
   -> 즉, a 또는 b로만 이루어진 문자열과 그렇지 않은 문자열을 구분해야 한다. 그래서 점수와 개수의 기준은 이러한 부분문자열들로 구분된다.
2. a또는 b로만 이루어진 문자열에서는 우선 점수가 더 높은 쪽의 쌍부터 맞춘다. a와 b의 개수를 하나씩 소모해야 한다.
3. 나머지 쌍을 맞춘다. 나머지 쌍의 개수는 min(나머지 a개수, 나머지b개수)이다.

이를 기반으로 프로시저를 정의할 수 있다. 문자열을 순차적으로 읽으며 다음을 따른다:

1. 만약 현재 글자가 a또는 b가 아니라면, 기존 min(a개수, b개수) * min(x, y)를 누적한다..
2. 만약 현재 글자가 a이면:
   만약 y가 더 크면, b의 개수를 하나 소모해서 ba만들고 점수 누적. 아니라면 a의 개수를 하나 늘림.
3. 만약 현재 글자가 b이면:
   만약 x가 더 크면, a의 개수를 하나 소모해서 ab만들고 점수 누적. 아니라면 b의 개수를 하나 늘림.

단, 짝지어 만들 수 없는경우, 예컨데 b를 읽었고 x가 더 큰데, a의 개수가 0이라면, 그냥 b의 개수를 하나 늘려야 한다.
 
마지막으로, 1번을 한번 더 진행한다. 마지막 a....b 또는 b....a의 부분문자열의 후순위작업이 되지 않았기 때문이다.

이전 a^*b^*또는 b^*a^*에 대한 작업이 되지 않았기 때문이다.

 a*b*또는 b*a*인 이유는, 중간에 ba, ab꼴은 모두 없앤다고 가정했기 떄문이다.
 

코드

C++

class Solution {
public:
    int maximumGain(string s, int x, int y) {
        int aCount = 0;
        int bCount = 0;
        int lesser = min(x, y);
        int ans = 0;

        for(char ch : s) {
            if(ch > 'b') {
                ans += min(aCount, bCount) * lesser;
                aCount = 0;
                bCount = 0;
            } else if(ch == 'a') {
                if(x < y && bCount > 0) {
                    bCount--;
                    ans += y;
                } else {
                    aCount++;
                }
            } else {
                if(x > y && aCount > 0) {
                    aCount--;
                    ans += x;
                } else {
                    bCount++;
                }
            }
        }

        ans += min(aCount, bCount) * lesser;
        return ans;
    }
};