[Programmers/Level 2/Java] 짝지어 제거하기

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

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

문제 설명

알파벳 소문자로 이루어진 문자열 s가 주어질 때, 같은 문자가 2개 붙어있는 짝을 찾아 제거한다.
짝을 제거한 나머지 문자열을 다시 이어 붙여 문자열을 모두 제거할 때까지 반복한다.
짝지어 제거하기를 성공적으로 수행할 수 있다면 1을, 아닐 경우 0을 리턴한다.

예)
baabaa -> bbaa -> aa -> 
짝지어 제거하기로 모두 제거할 수 있으므로 1을 리턴한다.

풀이

정확성 뿐만 아니라 효율성을 체크하는 문제로, 단순 for문으로 풀다가는 시간초과가 나기 쉽다.
Stack을 이용하면 간편하면서도 효율성을 챙길 수 있다.

문자열 S의 문자를 하나씩 순회하면서,
Stack의 top에 있는 문자가 현재 비교하는 문자와 같은 경우에는 Stack의 pop을 없애고,
Stack이 비어있거나 top과 다른 문자가 있는 경우에는 Stack에 넣는다.

문자열 s를 모두 순회한 후 Stack이 비어있다면 짝지어 제거하기를 성공적으로 수행한 것이고,
Stack에 데이터가 남아있다면 짝지어 제거하기가 실패한 경우이다.

import java.util.*;

class Solution
{
    public int solution(String s)
    {
        int answer = 0;
        Stack<Character> stackChar = new Stack<>();
        
        for(int i = 0; i < s.length(); i++)
        {
            if(!stackChar.isEmpty() && stackChar.peek() == s.charAt(i))
                stackChar.pop();
            else
                stackChar.push(s.charAt(i));
        }
        
        answer = (stackChar.isEmpty())? 1 : 0;
        
        return answer;
    }
}