프로그래머스 : 짝지어 제거하기(Java)

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

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

 

---

 

[풀이]

 

 처음에 문자열을 돌면서 i와 i+1번째의 문자가 동일하다면 replace 메소드를 사용하는 식으로 짰는데 이렇게 될 경우 시간복잡도에 의해 문제를 풀지 못한다. (다른 문제를 풀면서도 알게 된 것인데 replace메소드 자체가 내부적으로 메모리를 많이 사용하게 된다고 한다.)

 

 그래서 스택을 이용해서 풀면 보다 간단한 코드로, 효율성 좋게 통과할 수 있다. char 배열에서 이제 넣으려는 문자와 이미 들어가 있는 문자가 같다면 제거를, 다르다면 넣는 식으로 풀 수 있다.

 

---

 

[코드]

 

import java.util.*;
class Solution{
    public int solution(String s) {
        int answer = -1;

        Stack<Character> stack = new Stack<>();
        char[] s_arr = s.toCharArray();

        for (char c : s_arr) {
            if (stack.empty()) {
                stack.push(c);
            } else {
                if (stack.peek() == c) {
                    stack.pop();
                } else {
                    stack.push(c);
                }
            }
        }

        if (stack.empty()) {
            answer = 1;
        } else {
            answer = 0;
        }

        return answer;
    }
}