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

문제

짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다.

먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다.
그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다.

문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다.

예를 들어, 문자열 S = baabaa 라면

b aa baa → bb aa → aa →

의 순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다.

풀이

1차적으로 생각한 것은 반복을 한번만 돌리자 였다.
i - 1과 i를 비교해서 같으면 i를 감소시키며 조정시키는 것이다.
효율성 테스트에서 나가리가 되었다.
따지고 보면 i를 계속 조정하니 O(N)이 아닐수도...

문제를 보다보니 Stack을 사용하면 O(N)만에 가능할 것 같았다.
Stack이 비어있을 때와, 그렇지 않을때를 나누어서 peek을 하여 비교후 pop을 하는 것으로 구성하였다.

항상 스택을 사용하는 문제는 그 포인트가 한번에 캐치가 안되는 느낌이다...
그래도 이번엔 빨리 파악했으니 다음에도 더 잘할 수 있을 것이다.

import java.util.*;
import java.lang.*;

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

        for(int i = 0; i < s.length(); i++) {
            if (stack.isEmpty()) {
                stack.push(s.substring(i, i + 1));
            } else {
                String str = stack.peek();
                if (str.equals(s.substring(i, i + 1))) {
                    stack.pop();
                } else {
                    stack.push(s.substring(i, i + 1));
                }
            }
        }

        return stack.isEmpty() ? 1 : 0;
    }
}

https://github.com/Win-9/Algorism/tree/main/programers/%EC%A7%9D%EC%A7%80%EC%96%B4%20%EC%A0%9C%EA%B1%B0%ED%95%98%EA%B8%B0