[코테연습] 2696. Minimum String Length After Removing Substrings

- 문자열 / 스택 문제

 

https://leetcode.com/problems/minimum-string-length-after-removing-substrings/description/?envType=daily-question&envId=2024-10-07

 

- 문제분석

1. String s 에 문자열이 담겨있다.

2. s 에 포함되어있는 문자열 중, "AB", "CD" 가 있을 경우에 해당 문자열을 제거한다.

3. 제거하고 남은 문자열에도 위와 동일한 문자가 있을 경우에 제거한다.

 

- 문제풀이

> 스택 미사용

1. String s 에 indexOf 로 "AB" 또는 "CD" 문자가 있는지 여부를 확인한다.

2. 있을 경우에 replaceAll 함수로 "" 로 제거하고, s를 다시 제거된 문자열로 초기화한다.

3. 해당 방법을 while 문으로 반복하여 수행한다.

 

class Solution {
    public int minLength(String s) {

        String str = s;
        while(str.indexOf("AB") >= 0 || str.indexOf("CD") >= 0) {
            str = str.replaceAll("AB", "").replaceAll("CD", "");
        }

        return str.length();
    }
}

 

> 스택 사용

1. Stack<Character> 을 선언하여 Character 을 담을 스택을 초기화한다.

2. String s 를 반복문으로 개별 문자를 확인 할 수 있도록한다.

3. 문자가 'B' 일 경우에, Stack 에서 원소를 peek 하여 'A' 인지 확인한다.

4. 'A' 일 경우 pop 하여 제거한다.

5. 'CD' 도 동일하게 확인한다.

6. 아닐경우에는 문자를 그대로 Stack에 저장한다.

 

class Solution {
    public int minLength(String s) {

        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < s.length(); i++) {

            char c = s.charAt(i);

            //AB
            if (!stack.isEmpty() && c == 'B' && stack.peek() == 'A') {
                stack.pop();
            }
            //CD
            else if (!stack.isEmpty() && c == 'D' && stack.peek() == 'C') {
                stack.pop();
            } else {
                stack.push(c);
            }

        }


        return stack.size(); 
    }
}

 

 

> Python 코드

class Solution:
    def minLength(self, s: str) -> int:
        stack = []
        for i in range(len(s)) :
            if len(stack) != 0 and s[i] == "B" and stack[-1] == "A" :
                stack.pop(-1)
            elif len(stack) != 0 and s[i] == "D" and stack[-1] == "C" :
                stack.pop(-1)
            else :
                stack.append(s[i])
        return len(stack)