[12973] 짝지어 제거하기

✔ 짝지어 제거하기

[프로그래머스 12973]

문제 분석하기

문자를 하나씩 스택에 저장하면서 스택의 가장 윗 부분에 동일한 문자가 존재할 경우 함께 제거하도록 함

모든 문자를 스택에 집어 넣은 후, 스택이 비었다면 1을 반환, 비지 않았다면 0을 반환

손으로 풀어보기

1. 스택에 문자를 하나씩 집어 넣기
   • 스택의 가장 윗 부분(top)에 동일한 문자가 존재할 경우 함께 제거
   • 그렇지 않다면 스택에 넣어줌
2. 모든 문자를 스택에 집어 넣은 후, 스택이 비었다면 1을 반환, 비지 않았다면 0을 반환

슈도코드 작성하기

s(문자열)
answer(짝지어 제거하기를 성공적으로 수행할 수 있는지 여부) = 0
stack(문자를 넣을 스택)
for(i -> s의 길이만큼) {
    c(s의 i번째 문자)
    if(stack이 비어있다면)
        stack에 c 저장
    else if(stack의 top이 c와 동일하다면)
        stack의 top 제거
    else
        stack에 c 저장
}
if(stack이 비어있다면)
    answer = 1
answer 반환

코드 구현하기

/**
 * 12973) 짝지어_제거하기
 */
public class L023_12973 {
    // s(문자열)
    public int solution(String s) {
        // answer(짝지어 제거하기를 성공적으로 수행할 수 있는지 여부)
        int answer = 0;
        // stack(문자를 넣을 스택)
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            // c(s의 i번째 문자)
            char c = s.charAt(i);
            // stack이 비어있다면
            if (stack.isEmpty())
                // stack에 c 저장
                stack.push(c);
            // stack의 top이 c와 동일하다면
            else if (stack.peek() == c)
                stack.pop();
            // stack의 top이 c와 동일하지 않다면
            else
                // stack에 c 저장
                stack.push(c);
        }
        // stack이 비어있다면
        if (stack.isEmpty())
            // 성공이므로 1로 변경
            answer = 1;
        // answer 반환
        return answer;
    }

    // 테스트 케이스
    public static void main(String[] args) {
        L023_12973 solution = new L023_12973();

        String s = "baabaa";

        int result = solution.solution(s);

        System.out.println(result);
    }
}