[프로그래머스] 짝지어 제거하기 (JAVA/자바)

흶·2021년 9월 16일

알고리즘 프로그래머스

Algorithm

목록 보기

55/60

문제 링크

풀이

문제 그대로 따라가다가 효율성에서 0점이 나온 문제다. stack을 사용해서 for문 한번에 해결해야 한다.

앞에서부터 하나씩 스택에 넣는데, 가장 위에 있는 알파벳이 지금 넣을 알파벳과 같으면 짝지어지는 것이므로 스택에 넣지 않고 pop한다.

마지막 알파벳까지 확인했을 때, 스택이 비어있다면 모두 짝지어 제거된 것으로 알 수 있다.

코드

통과된 코드

import java.util.Stack;

class Solution{

    public int solution(String s){

        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < s.length(); i++) {
        
            // stack이 비어있으면 그냥 넣는다
            if(stack.isEmpty()){
                stack.push(s.charAt(i));
                continue;
            }

            // 짝지을 수 있으면 스택에 넣지 않고 pop
            if (stack.peek() == s.charAt(i)) { 
                stack.pop();
            }else{
                stack.push(s.charAt(i));
            }
        }

        // 스택이 비었으면 모두 짝지어 없어진 것!
        return stack.isEmpty() ? 1 : 0;
    }
}

효율성 제로 코드

class Solution{

    public int solution(String s){
        int answer = 0;

        OuterLoop:
        while(true) {
            boolean flag = false; // 제거된 게 있으면 true

            for (int i = 0; i < s.length() - 1; i++) {
                if (s.charAt(i) == s.charAt(i + 1)) {
                    if(s.length()==2){ // 마지막 2개가 짝지어지면
                        answer = 1;
                        break OuterLoop;
                    }

                    s = s.substring(0, i) + s.substring(i + 2);
                    flag = true;
                }
            }
            
            // 더이상 제거되는 게 없으면 break
            if(!flag) break;
        }

        return answer;
    }
}