[Programmers] LV2 - 짝지어 제거하기

https://programmers.co.kr/learn/courses/30/lessons/12973

코딩테스트 연습 - 짝지어 제거하기

 

 

문제 파악

 

1. 문자열 중에서 'aa'와 같이 같은 문자가 연속되어있다면 해당 부분을 제거 한 다음 문자열을 다시 만든다

2. 이 과정을 반복하여 공백으로 만들 수 있다면 1 아니라면 0을 return 한다.

 

처음에는 char key = 'a'를 이용해서 해당 문자열에 'aa'가 없을 때까지 반복하고 'bb'를 만들어서 replaceAll로 처리하였다.

 

로직은 맞았지만 효율성이나 시간 초과가 발생하였고 다른 방법을 찾다 보니 스택으로 해결이 가능하겠다 라는 생각이 들어 스택을 활용하여 문제를 풀었다.

 

import java.util.*;
class Solution
{
    public int solution(String s)
    {
        Stack<Character> st = new Stack<>();
        
        //홀수면 문자 모두 제거 불가
        if(s.length()%2 == 1){
            return 0;
        }
        
        for(int idx = 0;idx<s.length();idx++)
        {
            char c = s.charAt(idx);
            
            if(!st.isEmpty())
            {
                char top = st.peek();
                
                if(c == top){
                    st.pop();
                }
                else {
                    st.push(c);
                }
            }
            else{
                st.push(c);
            }
        }
        
        return st.isEmpty() ? 1 : 0;
        
    }
}