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

문제

 

 

 

분석

반복적으로 i 번째 텍스트와 i+1 텍스트를 비교해서 동일 하다면

Java 의 string의 remove를 써줘서 제거해 나간다.

 

* 하지만 시간 초과가 발생하여 고민을 하다가 스택으로 구현을 해보았다.

통과가 되었다.

 

구현1

효율성 실패

class Solution
{
    public int solution(String s)
    {
        int answer = -1;
        boolean flag = true;
        
        
        
        String tmpString = s;
        while(flag) {
            flag = false;
            for(int i = 0; i <tmpString.length()-1; i++) {
                if(tmpString.charAt(i) == tmpString.charAt(i+1)){
                    String removeString = Character.toString(tmpString.charAt(i));
                    removeString += Character.toString(tmpString.charAt(i));
                    tmpString = tmpString.replace(removeString, "");
                    flag = true;
                    break;
                }
            }
        }

        if(tmpString.length() == 0) {
            answer = 1;
        } else {
            answer = 0;    
        }
        
        return answer;
    }
}

 

 

결과1

 

 

 

구현2

효율성 성공

import java.util.*;


class Solution
{
    public int solution(String s)
    {
        int answer = -1;
        Stack<Character> stack = new Stack<>();
        
        String tmpString = s;
        for (char c : tmpString.toCharArray()) {
            if (!stack.isEmpty() && stack.peek() == c) 
            {
                stack.pop();
            } else {
                stack.push(c);
            }
        }
        
        
        if(stack.isEmpty()) {
            answer = 1;
        } else {
            answer = 0;
        }
        
        return answer;
    }
}

 

 

결과2

 

 

 

 

 

 

문제링크: https://programmers.co.kr/learn/courses/30/lessons/12973

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