[프로그래머스] 12973. 짝지어 제거하기

문제 링크

[프로그래머스] 12973. 짝지어 제거하기

풀이 과정

처음에는 아래와 같이 인덱스를 증가시키면서 같은 문자가 나오면 문자 두 개를 지우는 방식으로 구현했습니다.

public static int solution(String s) {
    int answer = 0;
    StringBuilder sb = new StringBuilder(s);
    int target = 0;

    while (target < sb.length() - 1 && sb.length() != 0) {
        if (sb.charAt(target) == sb.charAt(target + 1)) {
            sb.deleteCharAt(target);
            sb.deleteCharAt(target);

            if (target > 0)
                target--;
        } else
            target++;
    }

    if (sb.length() == 0)
        answer = 1;

    return answer;
}

하지만, 문자열이 매번 제거되는 문자들로만 이뤄져있다면 문자열의 최대 길이 백만으로 O(n^2)의 시간복잡도를 가지며, 실행시간 1000초로 시간 초과가 나게 됩니다.

앞에서부터 이어지는 문자열의 뒷 부분만 매번 확인하면 되므로 스택을 활용하게 되었습니다. 이로 인해 문자열의 길이만큼의 시간 복잡도 O(n)을 갖게 되며 시간 초과를 해결할 수 있습니다.

코드

import java.util.Stack;

public class Main {
    public static int solution(String s) {
        int answer = 0;
        Stack<Character> stack = new Stack();

        for (int i = 0; i < s.length(); i++) {
            if (stack.empty()) {
                stack.push(s.charAt(i));
            } else {
                if (stack.peek() == s.charAt(i)) {
                    stack.pop();
                } else
                    stack.push(s.charAt(i));
            }
        }

        if (stack.size() == 0)
            answer = 1;

        return answer;
    }

    public static void main(String[] args) {
//        String s = "baabaa";
        String s = "cdcd";

        System.out.println(solution(s));
    }
}