[프로그래머스] 짝지어 제거하기

class Solution
{
    public int solution(String s)
    {
        int answer = 0;

        while(true){
            String temp = s;
            for(int i=1; i<s.length(); i++){
                if(s.charAt(i)==s.charAt(i-1)){
                    String removeS = s.substring(i-1,i+1);
                    s = s.replaceFirst(removeS,"");
                    break;
                    }
                if(i==s.length()-1){
                    return 0;
                    }
            }
            
            if(s.length()==0){
                return 1;
            }
            
        }
    }
}

baabaa > bbaa > aa > null  이 되도록 s를 업데이트 시켜주며 null이 되면 1,  끝까지 읽었는데  null이아니면 0  이 되도록 짰다.

결과는 시간초과.

 

import java.util.*;

class Solution
{
    public int solution(String s)
    {
        int answer = 0;

        Stack<Character> st = new Stack<>();
        st.push(s.charAt(0));
        
        for(int i=1; i<s.length(); i++){
           if(st.isEmpty()){
               st.push(s.charAt(i));
           }else{
               if(st.peek() == s.charAt(i)){
                   st.pop();
               }else{
                   st.push(s.charAt(i));
               }
           }
        }
        
        if(st.isEmpty()){
            answer = 1;
        }else{
            answer = 0;
        }
        return answer;
    }
}

스택으로 풀어서 모두 통과하였다.

s의길이가 최대 100만일때, 약 100만개의 character을 모두 읽어야 해서 시간이 더 걸릴줄 알았는데,

문자열의  replace의 과정이 더욱 시간이 많이 걸리나 보다.