프로그래머스 - 짝지어 제거하기 문제 (자바)

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

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

스택을 이용하면 O(N) 시간복잡도로 풀수있어서 효율성까지 통과할 수 있는 문제

스택을 써야지라는 생각을 해내는게 이 문제의 핵심이다.

 

비어 있거나 스택 맨 위 값과 같지 않은 경우는 추가

비어 있지 않고 스택 맨 위 값과 같은 경우는 맨 위 값을 pop

 

baabaa를 처리할때 stack의 상태를 보면

[b] -> [b a] -> [b] -> [] -> [a] -> []

 

cdcd를 처리할때 stack의 상태를 보면

[c] -> [c d] -> [c d c] -> [c d c d]

import java.util.Stack;

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

        for (char c : s.toCharArray()) {
            if(stack.isEmpty() || stack.peek() != c) {
                stack.add(c);
            }else {
                stack.pop();
            }
        }

        int answer = 0;
        if (stack.isEmpty()) answer = 1;
        return answer;
    }
}