[LeetCode/Easy] 2696. Minimum String Length After Removing Substrings

1. Input

1) String s

 

2. Output

1) s에서 “AB" 또는 "CD”를 계속 없앨 때 나올 수 있는 결과 중 가장 짧은 길이를 반환

 

3. Constraint

1) 1 <= s.length <= 100

2) s는 영어 대문자로 이루어져 있다.

3) 문자를 없애고 나서 “AB" 또는 "CD"가 생길 수 있다.

 

4. Example

Input: s = "ABFCACDB" -> Output: 2

설명:

- "AB" 없애기 -> "FCACDB"

- "CD" 없애기 -> "FCAB"

- "AB" 없애기 -> "FC"

- 따라서 2를 반환한다.

 

5. Code

1) 첫 코드

class Solution {
    public int minLength(String s) {
        int ab = s.indexOf("AB"), cd = s.indexOf("CD");
        while(ab!=-1 || cd!=-1){
            if(ab!=-1) s = s.replace("AB","");
            if(cd!=-1) s = s.replace("CD","");
            ab = s.indexOf("AB"); cd = s.indexOf("CD");
        }
        return s.length();
    }
}

- 36%, 33%

2) 스택을 이용한 코드

class Solution {
    public int minLength(String s) {
        Stack<Character> stack = new Stack<>();
        int i = 0;
        while(i<s.length()){
            if(stack.empty()) stack.push(s.charAt(i));
            else if(stack.peek()=='A' && s.charAt(i)=='B') stack.pop();
            else if(stack.peek()=='C' && s.charAt(i)=='D') stack.pop();
            else stack.push(s.charAt(i));
            i++;
        }
        return stack.size();
    }
}

- 55%, 87%

- 힌트에 스택이 써있는건 다 이유가 있다!