짝지어 제거하기

import java.util.*;
class Solution{
    
    public int solution(String s)    {
        int answer = 0;
        Stack<String> st = new Stack<String>();
        String top = null, str = null;
 
        if (s.length() % 2 == 0) {
            for (int i = 0; i < s.length(); i++) {
                str = String.valueOf(s.charAt(i));
                if (!st.isEmpty()) {
                    top = st.peek();
                    if (top.equals(str))
                        st.pop();
                    else
                        st.push(str);
                } else
                    st.push(str);
            }
            if (st.size() == 0)
                answer = 1;
        }
        return answer;
    }
}

문자열 2개가 붙어있으면 제거하고 최종적으로 문자열이 남아있는지 확인하는 문제이다.

단순하게 replaceAll을 사용해서 해결했지만, 효율성에서 걸리게 되었다.

왜냐하면 전체 문자열을 여러 번 반복해서 확인하기 때문이다.

이를 해결하기 위해 Stack을 사용하였고, O(n)의 복잡도로 해결할 수 있었다.

문자열이 홀수인 경우를 필터링하고 스택의 상태를 확인하며 비교하였다.

 

replaceAll을 사용한 코드는 아래와 같다.

import java.util.*;
class Solution{
    
    public int solution(String s)    {
        int answer = 0;
        int len = s.length();
        while (len != 0) {
            s = s.replaceAll("(.)\\1", "");
            int tmp = s.length();
            if (len == tmp)
                break;
            else
                len = tmp;
        }
        if (len == 0)
            answer = 1;
        return answer;
    }
}

정규표현식을 사용하여 임의의 한 문자가 붙어있는 경우를 체크하였다.

Backreferences인 \\1 사용하여 (.)에서 나온 임의의 문자가 붙어있는 것을 확인한다.