짝지어 제거하기

무언가 짝을 짓는 문제는 Stack자료구조를 떠올린다.
Stack으로 구현했을때, 시간복잡도가 괜찮다면 바로 적용한다.

for문 로직은 어떻게 흘러가는가?
(1) 스택이 비어있으므로 item 값을 넣어준다.
(2) 스택이 비어있지 않은 경우에는 현재 item과 stack의 top부분의 값을 비교해서 같은 경우, 즉 짝짓기가 된 경우 스택에 존재하는 값을 제거해준다.
(3) 스택이 비어있지 않은 경우 (2)번경우가 아니라면 stack에 값을 추가해준다.
(4) 최종적으로 stack이 비어있어야 짝짓기가 가능한 경우이므로 answer값을 1로 초기화해준다.

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

        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < s.length(); i++) {

            char item = s.charAt(i);

            if(stack.isEmpty()){
                stack.add(item);
            }else{
                if(stack.peek() == item){
                    stack.pop();
                }else{
                    stack.add(item);
                }
            }
        }

        if(stack.isEmpty()){
            answer = 1;
        }

        return answer;
    }
}