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

문제

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

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

두번 반복되는 문자열을 골라 제거하는 문제입니다. 제거 후에 앞뒤에 있는 문자가 다시 두번 반복되면 해당 문자도 제거하는 식입니다. 문자열이니만큼 문자열 문제에서 자주 쓰이는 스택을 활용해 보겠습니다.

풀이

1. 문자열의 문자들을 스택에 하나씩 집어 넣습니다.
2. 만약 스택이 비어있지 않고 (이전에 집어넣은 문자가 존재하고), 스택의 peek값이 현재 집어 넣을 문자와 같다면 그 둘은 두번 반복되는 문자열이기 때문에 스택의 peek값을 pop합니다.
3. 아니라면 집어넣을 문자열을 push합니다.
4. 종료되었을 때 스택의 요소들이 전부 pop 되어 있다면 1을 아니라면 0을 반환합니다.

Java

import java.util.Stack;

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

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

Python

def solution(s):
    stack = []
    for char in s:
        if stack and stack[-1] == char:
            stack.pop()
        else:
            stack.append(char)
    return 1 if not stack else 0

제 생각엔 stack으로 푸는 방법이 가장 간결하고 이해하기 쉽게 푸는 방법같습니다. 하지만 다른 방법도 찾아보았을 때 스택 + 인덱스를 활용하는 풀이가 가장 많았던 것 같아서 이 내용도 한 번 리뷰해보겠습니다. 둘 다 시간 복잡도는 똑같이 O(N)이 될 것 같네요!

1. 문자열을 바이트 배열로 변환합니다.
2. 각 문자의 인덱스를 스택에 저장하여 두 문자가 짝인지 확인합니다. 이때 iLeft와 iRight를 사용하며 각각 현재 인덱스와 다음 인덱스를 나타냅니다. (두 문자가 같다면 짝임)
3. 스택이 비어있지 않은 경우 이전에 저장된 인덱스를 꺼내와 pop하고 이전 위치로 돌아가 다음 문자를 비교합니다.
4. 스택이 비버있는 경우는 더이상 비교할 문자가 없는 것이므로 두짝을 제거한 뒤의 인덱스로 건너뛰어 (iRight+1)한 후 새 영역으로 이동합니다.
5. 비교가 모두 끝났을 때 iLeft와 iRight가 문자열 길이를 넘어 선 경우 1 아닐 경우 0을 반환합니다.

Java

import java.util.Stack;

public class Solution {

    public static void main(String[] args) {
        System.out.println(solution("baabaa"));
    }

    public static 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]) {

                if (stack.empty()) {
                    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;
    }
}