[오늘의 문제] 짝지어 제거하기

출처: https://school.programmers.co.kr/learn/courses/30/lessons/12973#

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

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

b aa baa → bb aa → aa →

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

제한사항
문자열의 길이 : 1,000,000이하의 자연수
문자열은 모두 소문자로 이루어져 있습니다.
입출력 예
s result
baabaa 1
cdcd 0
입출력 예 설명
입출력 예 #1
위의 예시와 같습니다.
입출력 예 #2
문자열이 남아있지만 짝지어 제거할 수 있는 문자열이 더 이상 존재하지 않기 때문에 0을 반환합니다.

※ 공지 - 2020년 6월 8일 테스트케이스가 추가되었습니다.
※ 공지 - 2023년 8월 31일 테스트케이스가 추가되었습니다. 기존에 제출한 코드가 통과하지 못할 수도 있습니다.

내가 작성한 코드문

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

        // 알파벳 소문자로 이루어진 문자열을 가지고 시작
        // 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다.
        // 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다.
        // 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다
        
        StringBuilder sb = new StringBuilder(s);
        for(int i = 0; i < sb.length() - 1; ){//세번째 항 비우기 
            // 앞에게 같은 경우 둘다 ""로 replace
            
            if(sb.charAt(i) == sb.charAt(i + 1)){
                sb.delete(i, i + 2);// 두개 문자열을 제거 
                // sb.deleteCharAt(i);
                // sb.deleteCharAt(i + 1);
                // s = s.replace(String.valueOf(s.charAt(i)), "");// ''는 빈 문자 리터럴인데, 자바에서는 허용되지 않는다.
               // 빈 문자열로 바꾸려면 replace(String, String)을 써야
                // s.charAt(i) = s.charAt(i + 1);
                 i = Math.max(0, i - 1);// 앞글자와 다시 비교하기 위해 당기기
                 // i--;
            } else {
                i++;
            }
        } 
        
        if(sb.length() == 0){
            answer = 1;
        } else {
            answer = 0;
        }
        
        // if(sb.toString().equals("")){// 성공적으로 수행할 수 있으면 1을
        //     answer = 1;
        // } else {// 아닐경우
        //     answer = 0;
        // }

        return answer;
    }
}

스트링 빌더를 써야 한다는 생각을 하고

스트링 빌더 메서드를 알아내야 했다.

채점 결과
정확성: 61.2
효율성: 0.0
합계: 61.2 / 100.0

효율성에선 0점이 뜬다.

StringBuilder.delete() 연산이 반복되면서 전체 시간복잡도가 매우 비효율적이기 때문

StringBuilder.delete(i, i+2) 는 내부적으로 문자 배열을 shift(이동) 하기 때문에 O(N)의 비용이 든다.

그런데 이걸 매번 루프 안에서 최대 수만 개 가까이 반복하면 → 총 시간복잡도는 O(N²)
➡ 긴 문자열일 경우 시간 초과 발생 → 효율성 테스트 실패

✅ 해결 방법: Stack을 이용한 O(N) 풀이로 변경
스택을 쓰면 한 번의 문자열 순회로 해결할 수 있어서 O(N)에 처리 가능하며, 효율성도 통과한다.

스택을 활용한 풀이

import java.util.Stack;

class Solution {
    public int solution(String s) {
        Stack<Character> stack = new Stack<>();

        for (char ch : s.toCharArray()) {
            if (!stack.isEmpty() && stack.peek() == ch) {
                stack.pop(); // 짝이 맞으면 제거
            } else {
                stack.push(ch); // 아니면 스택에 넣기
            }
        }

        return stack.isEmpty() ? 1 : 0;
    }
}

다른 사람의 풀이

import java.util.*;

class Solution
{
    public int solution(String s)
    {
        int answer = 0;
        Stack<Character> stack = new Stack<>();

        for(char c : s.toCharArray()){
            if(stack.size() == 0){
                stack.push(c);
            }
            else if(stack.peek() == c){
                stack.pop();
            }
            else{
                stack.push(c);
            }
        }


        return stack.size() > 0 ? 0 : 1;
    }
}

스택 안쓰는 사람이 없었다.

import java.util.Stack;

class Solution
{
    public int solution(String s)
    {

        byte[] bytes = s.getBytes();
        int length = bytes.length;

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

        int iLeft = 0, iRight = iLeft + 1;
        for (; iLeft < length && iRight < length; ) {
            if (bytes[iLeft] == bytes[iRight]) {
                // bytes[iLeft] = 0;
                // bytes[iRight] = 0;

                if (stack.empty()) {
                    /*
                    while (iLeft >= 0 && bytes[iLeft] == 0) iLeft--;
                    while (iRight < length && bytes[iRight] == 0) iRight++;

                    if (iLeft < 0) iLeft = iRight;
                    if (iRight <= iLeft) iRight = iLeft + 1;
                    */

                    iLeft = iRight + 1;
                    iRight = iLeft + 1;
                } else {
                    iLeft = stack.pop();
                    iRight++;
                }
            } else {
                stack.push(iLeft);

                iLeft = iRight;
                iRight = iLeft + 1;
            }
        }

        return iLeft >= length && iRight >= length ? 1 : 0;
    }
}