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

문제

문제 설명

짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다.

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

b aa baa → bb aa → aa →

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

제한사항

1. 문자열의 길이 : 1,000,000이하의 자연수
2. 문자열은 모두 소문자로 이루어져 있습니다.

입출력 예

풀이

잘못된 접근방법

정규식을 사용하여서 정해진 문법 안에서 하나씩 소거하는 방법을 생각했었습니다. 하지만 같은 문자 반복을 표시하는 규칙을 사용했을 때 a-z 사이에 포함되는 문자열이 2개 연속 나오면 소거가 되기에 문자가 해결되지 않는다는 것을 깨달았습니다.

새로운 접근방법

Stack을 이용하였습니다. 이유는 문자열에서 하나씩 Stack으로 옮길 때 최근 입력된 문자(Stack Peek)와 입력할 문자(Current)를 비교하여서 동일한 문자라면 Stack에 입력된 문자를 pop으로 뽑아냄으로 2연속으로 사용된 문자를 제거하는 방식을 사용하였습니다.

import java.util.*;

class Solution
{
    public int solution(String s)
    {
        Stack<String> answer = new Stack<String>();
        
        for(int i = 0; i < s.length(); i++)
        {
            if(answer.isEmpty())
                answer.push(String.valueOf(s.charAt(i)));
            else 
            {
                String peekData = answer.peek();
                String currentData = String.valueOf(s.charAt(i));
                
                if(peekData.equals(currentData))
                    answer.pop();
                else
                    answer.push(String.valueOf(s.charAt(i)));
            }
        }
        
        return answer.size() == 0 ? 1 : 0;
    }
}