[JAVA 문제 풀이] 396. Maximum Score From Removing Substrings

Maximum Score From Removing Substrings - LeetCode

Can you solve this real interview question? Maximum Score From Removing Substrings - 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.   Example 1: Input: s = "cdbcbbaaabab", x = 4, y = 5 Output: 19 Explanation: - Remove the "ba" underlined in "cdbcbbaaabab". Now, s = "cdbcbbaaab" and 5 points are added to the score. - Remove the "ab" underlined in "cdbcbbaaab". Now, s = "cdbcbbaa" and 4 points are added to the score. - Remove the "ba" underlined in "cdbcbbaa". Now, s = "cdbcba" and 5 points are added to the score. - Remove the "ba" underlined in "cdbcba". Now, s = "cdbc" and 5 points are added to the score. Total score = 5 + 4 + 5 + 5 = 19. Example 2: Input: s = "aabbaaxybbaabb", x = 5, y = 4 Output: 20   Constraints: * 1 <= s.length <= 105 * 1 <= x, y <= 104 * s consists of lowercase English letters.

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

문자열 s와 정수 x와 y 두 개가 주어집니다.
두 가지 유형의 연산을 여러 번 수행할 수 있습니다.

* 부분 문자열 "ab"을 제거하고 x점을 얻습니다.
 * 예를 들어, "ab"를 "cabxbae"에서 제거하면 "cxbae"가 됩니다.
* 부분 문자열 "ba"를 제거하고 y점을 얻습니다.
 * 예를 들어, "cabxbae"에서 "ba"를 제거하면 "cabxe"가 됩니다.

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

제약 조건:
* 1 <= s.length <= 105
* 1 <= x, y <= 104
* s는 소문자로 구성되어 있습니다.

내가 작성한 코드 1 (시간 초과)

class Solution {
    public int maximumGain(String s, int x, int y) {
        int answer = 0;

        // 둘 중에 큰 값에 따라 바뀔 변수
        String first = "";
        String second = "";

        // x, y 큰 값 설정
        int max = Math.max(x, y);
        int min = Math.min(x, y);

        // 둘 중에 큰 값의 쌍을 먼저 확인하도록 변수 값 변경
        if (x > y) {
            first = "ab";
            second = "ba";
        } else {
            first = "ba";
            second = "ab";
        }

        while (true) {
            if (s.contains(first)) {
                answer += max;
                s = s.replaceFirst(first, "");
                continue;
            }

            if (s.contains(second)) {
                answer += min;
                s = s.replaceFirst(second, "");
                continue;
            }

            break;
        }

        return answer;
    }
}

내가 작성한 코드 2 (최적화)

import java.util.*;

class Solution {
    public int maximumGain(String s, int x, int y) {
        int answer = 0;
        Stack<Character> stack = new Stack<>(); // 큰 점수 쌍을 처리하기 위한 임시 저장 스택
        Stack<Character> stack2 = new Stack<>(); // 첫 번째 처리 후 남은 문자에서 작은 점수 쌍을 처리하기 위한 스택

        // 점수가 더 큰 쌍부터 먼저 처리
        String first = "";
        String second = "";

        // x, y 큰 값 설정
        int firstScore = Math.max(x, y);
        int secondScore = Math.min(x, y);

        // 둘 중에 큰 값의 쌍을 먼저 확인하도록 변수 값 변경
        if (x > y) {
            first = "ab";
            second = "ba";
        } else {
            first = "ba";
            second = "ab";
        }

        // 스택에 담아가면서 큰 점수 쌍 처리
        for (char c : s.toCharArray()) {
            if (!stack.isEmpty() && stack.peek() == first.charAt(0) && c == first.charAt(1)) {
                stack.pop();
                answer += firstScore;
            } else {
                stack.push(c);
            }
        }

        // 작은 점수 쌍 처리
        while (!stack.isEmpty()) {
            char c = stack.pop();
            if (!stack2.isEmpty() && c == second.charAt(0) && stack2.peek() == second.charAt(1)) {
                stack2.pop();
                answer += secondScore;
            } else {
                stack2.push(c);
            }
        }

        return answer;
    }
}

• 반복문 방식
• 문자열을 여러 번 순회하며 쌍을 탐색 → 느림

• 스택 사용
• 문자를 한 글자씩 확인하며 쌍을 즉시 처리 → 빠름