🎈 문제 풀이

이 문제는 스택(Stack) 자료구조를 활용하여 주어진 문자열에서 짝지어 있는 문자를 찾아서 제거할 수 있는지를 판단하는 문제입니다. 스택은 그 자체로는 LIFO 자료구조이지만 활용 예시를 아는 것이 중요합니다. 코딩테스트/알고리즘 문제풀이에서 스택이 사용되는 사례는

1. 데이터를 짝지어 처리하고자 할 때
2. 뒤로 가기를 구현할 때

가 대표적입니다. 이 문제는 1번을 위해 스택을 사용하는 문항이라 볼 수 있겠습니다.

우선 문제 조건에 주어진 대로 주어진 문자열을 한 글자씩 순회하면서 스택에 추가하고, 스택의 탑(top)에 있는 문자와 현재 문자가 같으면 스택에서 제거합니다.

이러한 과정을 거치고 남은 스택의 크기를 검사하여 모든 짝지어 제거하기 과정을 성공적으로 완료할 수 있는지를 판단합니다.

위에서 제시한 코드는 주어진 문자열을 한 글자씩 순회하면서 스택을 활용하여 짝지어 제거하기 과정을 구현한 것입니다. 각 문자를 순회하면서 스택의 탑(top)에 있는 문자와 현재 문자가 같으면 스택에서 제거하고, 다르면 스택에 추가합니다. 이러한 과정을 모든 문자를 순회하면서 반복합니다.

그리고 최종적으로 스택이 비어있는지를 검사하여, 스택이 비어있으면 1을 반환하고, 그렇지 않으면 0을 반환합니다.

import java.util.Stack;

class Solution {
    public int solution(String s) {
        Stack<Character> stack = new Stack<>();

        for (char c : s.toCharArray()) {
						// 스택의 탑과 현재 문자가 같으면 짝 지어서 제거 가능
            if (!stack.isEmpty() && stack.peek() == c) { 
                stack.pop();
            } else {
                stack.push(c); // 스택에 추가
            }
        }

        return stack.isEmpty() ? 1 : 0;
    }
}