Sho1007

MMORPG 클라이언트 개발자 지망생

3 minute read

1717. Maximum Score From Removing Substrings / c++ / Medium / 52분

문제 및 코드

문제 링크

class Solution {
    int FindAB(string& s)
    {
        int count = 0;

        string result = "";

        for (int i = 0; i < s.length(); ++i)
        {
            if (s[i] == 'b')
            {
                if (result.length() > 0 && result.back() == 'a')
                {
                    result.pop_back();
                    count++;
                    continue;
                }
            }

            result.push_back(s[i]);
        }

        s = result;

        return count;
    }
    int FindBA(string& s)
    {
        int count = 0;

        string result = "";

        for (int i = 0; i < s.length(); ++i)
        {
            if (s[i] == 'a')
            {
                if (result.length() > 0 && result.back() == 'b')
                {
                    result.pop_back();
                    count++;
                    continue;
                }
            }

            result.push_back(s[i]);
        }

        s = result;

        return count;
    }
    int FindABThanBA(string s, int x, int y)
    {
        int result = 0;

        result += FindAB(s) * x;

        result += FindBA(s) * y;

        return result;   
    }

    int FindBAThanAB(string s, int x, int y)
    {
        int result = 0;

        result += FindBA(s) * y;

        result += FindAB(s) * x;

        return result;   
    }
public:
    int maximumGain(string s, int x, int y) {
        int result = 0;
        string subString = "";
        for (int i = 0; i < s.length(); ++i)
        {
            if (s[i] == 'a' || s[i] == 'b')
            {
                subString += s[i];
            }
            else if (subString.length() > 0)
            {
                int resultA = FindABThanBA(subString, x, y);
                int resultB = FindBAThanAB(subString, x, y);

                result += resultA >= resultB ? resultA : resultB;
                subString = "";
            }
        }

        if (subString.size() > 0)
        {
            int resultA = FindABThanBA(subString, x, y);
            int resultB = FindBAThanAB(subString, x, y);

            result += resultA >= resultB ? resultA : resultB;
        }

        return result;
    }
};

접근 방식

문자열 / 탐욕법

  1. 임의의 문자 s에서 “ab”와 “ba”가 존재하면 제거한다.
  2. 이 때 “ab”를 제거하면 점수에 x를 더하고, “ba”를 제거하면 점수에 y를 더한다.
  3. 위의 과정을 몇 번이고 수행한 뒤, 나올 수 있는 최고 점수를 반환하는 문제였다.
  4. 이를 해석해보면, 괄호 문제 + 탐욕법이 섞여 있는 문제였다.
    1. AB 혹은 BA로 짝을 찾아 연쇄적으로 제거해 나가는 부분은 괄호(스택)문제이고,
    2. x 와 y 의 값에 따라 항상 “ab”를 먼저 제거할지, “ba”를 먼저 제거할지를 정하는 부분은 탐욕법(그리디 알고리즘)이라고 볼 수 있다.
  5. 문제를 풀다보니, “ab”가 나올 때마다 제거하면, 제거한 뒤 결과 문자열에는 “ba”만 나올 수 있고,
  6. “ba” 가 나올 때마다 제거하면, 제거한 뒤 결과 문자열에는 “ab”만 나올 수 있었다.
  7. 위의 규칙을 토대로 시작 문자열 s를 순회하며 아래 로직을 수행
    1. s[i]가 ‘a’나 ‘b’면, subString 에 더해준다.
    2. s[i]가 ‘a’, ‘b’이외의 값이고, subString이 비어있지 않다면,
      1. “ab”를 먼저 찾고, “ba”를 찾은 점수와
      2. “ba”를 먼저 찾고, “ab”를 찾은 점수를 비교하여
      3. 더 큰 점수를 최종 점수에 더해준다.
  8. 하지면 여기서 문제가 생겼었다.
  9. 항상 풀던대로 스택을 사용하여 문제를 풀다보니, 첫 번째 “ab” 혹은 “ba”를 찾을 때는 괜찮았는데, 그 결과값으로 다시 “ba” 혹은 “ab”를 찾으려고 할 때, 스택을 돌면서, 만약 원하는 값이 아니면, 현재 스택과는 또다른 스택 즉 Stack2에 그 결과값을 넣어야 연쇄 반응을 검사할 수 있었는데, 그러지 않고 그냥 현재값을 버려버렸더니, 연쇄반응을 체크하지 못해 틀린 값이 나왔었다. 
    // 예시
/*
* "ab"를 찾고 나온 결과 문자열이 "bbaa" 라고 할 때,
* 스택에 쌓여 있으므로
* a (top)
* a
* b
* b
* 순으로 쌓여 있다.
* 이 때, top인 'a'를 검사했을 때, 다음 스택의 top이 'b'가 아니므로,
* 이 값을 Stack2라는 스택에 저장해야, 중간 "ba"를 검출하여 제거한 뒤
* 다시 "ba"를 한번 더 찾을 수 있는데, 그러지 않고 그냥 top 'a'를 버렸던 것이다.
*/
  10. 이 실수를 찾는데 시간을 꽤 소모했다.
  11. 그래서 다음엔 스택을 사용하지 않고, 제거되지 않는 값을 문자열로 만들어서 다음 검사에 넘기는 식으로 풀었다.
    (s -> FindAB(s) -> FindBA(s))
  12. 해결

생각해 볼 점

  1. 처음 “ab”나 “ba”를 지울 때는, 맞지 않은 문자를 스택에 저장할 생각을 해놓고, 왜 두 번째 “ba”나 “ab”를 지울 때는, 맞지 않는 값을 그냥 버렸는지 모르겠다.
  2. 시간 효율이 다른 사람들에 비해 많이 떨어지는 걸 보니 더 효율적인 방법이 있는 것 같다.
  3. 전체적인 로직을 미리 짜두고 하나씩 작성했어야 했는데, 이번에는 괄호 문제라 쉽게 생각하고 손이 먼저 나갔던 것 같다. 항상 전체적인 로직을 먼저 짜는 습관을 들여야겠다.

You may also enjoy