12973 짝지어 제거하기

✏️ 문제 설명

짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다.
먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다.
그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다.
이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다.
문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요.
성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다.

예를 들어, 문자열 S = baabaa 라면

b aa baa → bb aa → aa →

의 순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다.

✏️ 제한사항

• 문자열의 길이 : 1,000,000이하의 자연수
• 문자열은 모두 소문자로 이루어져 있습니다.

✏️ 입출력 예

s	result
baabaa	1
cdcd	0

✏️ 문제 풀이

📍 1차 시도 - 실패

문제 자체는 쉽지만 문제를 보자마자 효율성을 통과시키는 것이 핵심이라고 생각했다.

어떻게 하면 가장 효율적일 지 생각했고,

루프를돌려 처음부터 하나하나 반복되는 글짜가 있을경우 replace 모두 제거하고 다시 반복하는 식으로 문제를 해결했다.

역시 결과는 효율성에서 한가지만 통과하고 모두 실패 했다.

이 방법으로는 해결이 어려울 것 같다.

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

        boolean check = true;
        while (check) {
            check = false;
            for (int i = 0; i < s.length(); i++) {
                try {
                    if (s.charAt(i) == s.charAt(i + 1)) {
                        String alp = String.valueOf(s.charAt(i));
                        s = s.replace(alp + alp, "");
                        check = true;
                        break;
                    }
                }catch (Exception e){}
            }
        }
        answer = s.length() == 0 ? 1:0;
        return answer;
    }
}

📍 2차 시도 - 실패

한 자 씩 확인하다 중복이 발견되면 replace 로 제거하고,

i 값에 -2 로 바로 전 index 로 돌아가 작업을 반복하는 식으로 코드를 개선했다.

테스트 케이스가 확실히 빨라졌지만

결과는 1차와 동일하게 효율성에서 1문제 제외하고 시간초과로 실패했다.

class Solution{
    public int solution(String s) {

        for (int i = 0; i <= s.length(); i++) {
            try {
                if (s.charAt(i) == s.charAt(i + 1)) {
                    String alp = String.valueOf(s.charAt(i));
                    s = s.replace(alp + alp, "");
                    i -= 2;
                }
            } catch (Exception e) {
            }
        }
        return s.length() == 0 ? 1 : 0;
    }
}

📍 3 차 시도 - 실패

stack 을 사용하면 효율이 좋아진다고 해서 stack 으로 문제를 해결해 봤다.

확실히 속도가 매우 빨라졌지만

효율성에서 계속 통과하던 2번 test 에서 시간초과가 발생했다..

import java.util.Stack;

class Solution {
    public int solution(String s) {
        
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            try {
                if (s.charAt(i) == stack.peek()) {
                    stack.pop();
                    continue;
                }
            }catch (Exception e){}
            stack.push(s.charAt(i));
        }
        return stack.empty() ? 1 : 0;
    }
}

📍 4차 시도 - 성공

아무리 생각해도 효율성을 높일 방법이 떠오르지 않아서 try / catach 를 제거하고 if 에 조건문을 하나 더 달아서 문제를 해결해봤다.

결과는 성공이였고,
try / catch 의 효율이 좋지 않다는 것을 깨닳았다.

import java.util.Stack;

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