짝지어 제거하기

문제정의

---

연달아 등장하는 알파벳을 짝지어 삭제한다고 할 때, 모든 문자열을 삭제할 수 있는지 확인하는 문제이다.

문제풀이

---

전체 코드는 다음과 같다.

package level2;

import java.util.Stack;

public class PairRemove {

    //프로그래머스 문제풀이 Level2 짝지어 제거하기
    public static void main(String[] args) {
        String s = "baabaa";
        int answer = 0;
        Stack<Character> stack = new Stack<>();
        
        for(char c : s.toCharArray())
        {
            if(!stack.empty())
            {
                if(stack.peek() == c)
                {
                    stack.pop();
                    continue;
                }
                    
            }
            stack.push(c);
        }
        if(stack.empty())
            answer = 1;

        System.out.println(answer);
    }
    
}

처음에는 리스트에 넣고 remove를 통해 제거했는데 아무래도 시간이 오래 걸려서 효율성을 통과하지 못했다. 그래서 고민하던 도중 스택을 활용하면 되겠다는 생각이 들어 코드를 위와 같이 작성했다.

1. 스택이 비어있다면 문자를 넣는다.
2. 스택이 비어있지 않다면 top을 확인한다. 만약 스택의 탑과 들어올려는 값이 같으면 짝지어 지는 경우이므로 스택에서 제거하고 다음 원소에 대해 1,2번과정을 본다.
3. 모든 과정을 마쳤을 때, 스택이 비어있다면 1을 반환한다.

최종 시간복잡도는 \(O(n)\)이다.

테스트