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

문제

https://programmers.co.kr/learn/courses/30/lessons/12973

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

풀이

처음엔 문자열의 문자에 대해 탐색을 돌리면서 문자열을 자르고 붙이고를 반복하며 풀었다가 정확성은 100점을 맞았지만 효율성에서 0점을 받아 이후 Stack을 통해서 해결할 수 있었다. Stack을 이용하면 O(n)으로 해결할 수 있다.

문자열의 모든 원소들에 대해 하나씩 확인해 주면서 Stack의 top과 이제 들어올 문자가 같으면 제거할 수 있으므로 해당 문자를 넣지 않고, Stack의 top을 제거해 준다. 이러면 연속되는 같은 두 문자를 제거할 수 있다.

하지만 Stack의 top과 다르다면 제거할 수 없으므로 그냥 Stack에 넣어주었다. 이러한 행위를 반복해서 Stack에 들어오는 연속되는 문자들은 계속 제거되고, 남아있는 문자는 또 다시 들어올 문자와 비교해 줄 수 있어 최종적으로 모든 짝을 제거할 수 있으면 Stack의 크기가 0이 되고, 아니면 1 이상이 될 것이다.

문제를 풀면서 주의할 점은 Stack에 아무것도 들어있지 않은데 Stack의 top을 참조하려 하면 Exception이 날 수 있으니 Stack의 크기가 0일 때는 무조건 Stack에 해당 문자를 넣어주도록 코드를 작성해야 한다.

 

정답 코드

import java.util.Stack;

class Solution
{
    public int solution(String s)
    {
        int answer = -1;

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

        for(int i = 0; i < s.length(); i++) {
            if(st.size() == 0) {
                st.push(s.charAt(i));
                continue;
            }
            if(st.peek() == s.charAt(i)) {
                st.pop();
            }
            else {
                st.push(s.charAt(i));
            }
        }

        answer = st.size() == 0 ? 1 : 0;

        return answer;
    }
}

효율성 0점 코드

class Solution
{
    public int solution(String s)
    {
        int answer = -1;

        StringBuilder sb = new StringBuilder(s);

        while (true) {

            boolean flag = false;

            for(int i = 0; i < sb.length() - 1; i++) {

                if(sb.charAt(i) == sb.charAt(i + 1)) {
                    sb.deleteCharAt(i);
                    sb.deleteCharAt(i);
                    flag = true;
                }
            }

            if(sb.length() == 0) {
                answer = 1;
                break;
            }
            if(flag == false) {
                answer = 0;
                break;
            }
        }
        return answer;
    }
}