짝지어 제거하기

유태형·2022년 3월 15일

프로그래머스 - Level 2

목록 보기

31/36

문제

문제 분석

2개의 동일한 문자가 있으면 제거합니다. 만약 제거후 또 2개의 동일한 문자가 존재한다면 존재하지 않을때까지 제거합니다. 만약 가능한 2개의 동일한 문자들을 모두 제거하였을때 남은 문자가 없다면 1, 있으면 0을 리턴합니다.

풀이

2개의 문자를 제거한다가 핵심이었습니다. 3개, 4개, ....n개 연속한 문자열을 모두 처리할 줄 알고 String.substring()을 이용하여 앞뒤 문자열을 다시 재조합 하였으나 효율성 문제로 Stack을 이용하여 해결하였습니다.

Stack

문제에서 n개의 연속된 동일한 문자가 아닌 2개의 연속된 동일한 문자입니다. 현재만 비교하면되어서 다음 문자열을 비교할 필요는 없습니다. 스택을 이용하면 효율성도 좋고 이해하기도 쉽습니다.

		Stack<String> stack = new Stack<>();
        String[] arr = s.split("");
        
        for(String input : arr){
            if(!stack.isEmpty() && stack.peek().equals(input)) //2개가 붙어 있는 짝
                stack.pop();
            else // 다른 문자
                stack.push(input);
        }

비어있거나, 스택의 TOP에 위치한 문자와 다르면 스택.push(), 반대로 스택의 TOP에 위치한 문자와 같으면 스택.pop()하여 이전문자와 비교만 하면 됩니다.

코드

import java.util.*;

class Solution
{
    public int solution(String s)
    {
        int answer = 0;
        Stack<String> stack = new Stack<>();
        String[] arr = s.split("");
        
        for(String input : arr){
            if(!stack.isEmpty() && stack.peek().equals(input)) //2개가 붙어 있는 짝
                stack.pop();
            else // 다른 문자
                stack.push(input);
        }
        
        if(stack.isEmpty()) //비어있다면, 모두 짝지을 수 있다면
            answer = 1;
        
        return answer;
    }
}