[알고리즘 문제] programmers - 짝지어 제거하기

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

코딩테스트 연습 - 짝지어 제거하기 | 프로그래머스

문제는 문자열에서 같은 알파벳이 2개 붙어있는 짝을 찾아 제거하고, 제거한 뒤 앞뒤의 문자열을 이어 붙입니다. 이후 앞의 과정을 짝이 발견되지 않을 떄까지 반복합니다. 만약 위의 과정을 반복해서 문자열을 모두 없앨 수 있으면 1, 그렇지 않으면 0을 출력합니다.

 

예를 들어 baabaa의 경우  baabaa → bbaa → aa →""식으로 제거할 수 있습니다.

 

처음에는 문제에서 제시한 대로 substring으로 짝을 기준으로 앞 뒤의 문자열을 잘라서 이어 붙이는 방식으로 했습니다. 그러니깐 시간초과가 나왔습니다. 찾아보니 substring()의 시간복잡도가 O(n)였습니다.

 

두번째 방법은 스택을 사용했는데 문자열의 각 문자를 순회하면서 스택에에 있는 값과 같으면 빼고 그렇지 않으면 다시 넣는 방식으로 진행했습니다. 

 

예를 들어, "qweewq"의 경우,

"q" : 아무것도 없기 때문에 push

"w" : peek하면 "q"가 있기 때문에 push

"e" : peek하면 "w"가 있기 때문에 push

"e" : peek하면 "e"가 있고 같기 때문에 pop

"w" : peek하면 "w"가 있고 같기 때문에 pop

"q" : peek하면 "q"가 있고 같기 때문에 pop

마지막으로 stack에 값이 하나도 없으면 1 하나라도 있으면 0을 출력합니다.

 

import java.util.*;

class Solution {
    public int solution(String s) {

        Stack stack = new Stack();

        for (int i = 0; i < s.length(); i++) {

            char c = s.charAt(i);

            if (!stack.empty() && (char) stack.peek() == c) {
                stack.pop();
            } else {
                stack.push(c);
            }
        }

        if (stack.empty()) {
            return 1;
        }
        return 0;
    }
}