2390. Removing Stars From a String (Stack)

<아이디어>

'*' 가 나올 경우 바로 앞에 있는 요소를 제거해야 한다는 점에서 선입선출 FIFO 개념인 Stack을 생각을 할 수 있었고

Stack의 담은 문자들을 하나로 합치는데 시간을 단축 시키기 위해 StrringBuilder를 생각 할 수 있었다.

 

<코드>

import java.util.Stack;

class Solution {
    // 시간 복잡도 O(n) 공간 복잡도 O(n)
    public String removeStars(String s) {
        Stack<Character> stack = new Stack<>();
        StringBuilder ans = new StringBuilder();

        for (int i = 0; i < s.length(); i++) {
            char unit = s.charAt(i);
            if(unit!='*')
                stack.push(unit);
            else
                stack.pop();
        }

        for (Character character : stack)
            ans.append(character);

        return ans.toString();
    }
}

 

+ 해당 문제를 Stack을 사용하지 않고 구현으로 풀 경우

이점: Stack을 사용한 것과 시간 복잡도 자체는 같지만 Stack의 push pop의 사전 과정이 필요가 없기 때문에 더 빠른 속도를 가지고 있다.

class Solution2 {
	// 시간 복잡도 O(n) 공간 복잡도 O(n)
    public String removeStars(String s) {
        int len = s.length();
        char[] chars = new char[len];
        int index = len, count = 0;
		// 문자열 s의 뒤에서 부터 시작
        for (int i = len - 1; i >= 0; i--) {
            char c = s.charAt(i);
            // *이 오면 제거해야할 문자 수 count++
            if (c == '*') {
                count++;
            } 
            // *이 아니고 제거해야 할 문자가 아니라면 char 배열에 추가
            else {
                if (count > 0) {
                    count--;
                } else {
                    chars[--index] = c;
                }
            }
        }
        // char 배열의 마지막으로 추가한 문자의 인덱스 부터 ~ 유효한 마지막 인덱스 까지의 범위 를 바탕으로 문자열을 만들어 반환 
        return String.valueOf(chars, index, len - index);
    }
}