문제

첫 번째 풀이 (시간초과)

로직

문자열을 리스트로 변환한다.
리스트의 0 번째 인덱스부터 마지막 인덱스까지 반복문을 실행한다.
해당하는 인덱스의 값과 그 다음 인덱스의 값이 동일할 경우 두 값 모두 삭제하고 0 번째 인덱스부터 다시 반복문을 실행한다.

코드

import java.util.*;

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

        List<String> strList = new ArrayList<>(Arrays.asList(s.split("")));
        
        int idx = 1;
        
        while (true) {
            if (idx >= strList.size()-1) {
                break;
            }
            
            if (strList.get(idx).equals(strList.get(idx+1))) {
                strList.remove(idx);
                strList.remove(idx);
                idx = 0;
            }
            else {
                idx ++;
            }
        }

        return strList.size() == 0 ? 1 : 0;
    }
}

결과

대부분 시간 초과가 났다.

2번째 풀이

로직

stack을 이용한다.
인덱스 0부터 문자열의 길이만큼 반복문을 실행한다.
stack이 비어 있거나 마지막 값이 현재의 값과 다를 경우에는 stack에 값을 넣는다.
마지막 값이 현재의 값과 동일할 경우에는 stack의 마지막 값을 제거한다.

모든 반복문을 실행한 후 탈출했을 때 stack이 비어 있으면 1을 반환하고 비어 있지 않으면 0을 반환한다.

코드

1. ArrayList 이용

import java.util.*;

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

        List<String> stack = new ArrayList<>();
        String[] strArr = s.split("");
        
        for (int i = 0; i < s.length(); i ++) {
            if (stack.size() == 0 || !stack.get(stack.size()-1).equals(strArr[i])) {
                stack.add(strArr[i]);
            }
            else {
                stack.remove(stack.size()-1);
            }
        }
        
        return stack.size() == 0 ? 1 : 0;
    }
}

2. Stack 이용

import java.util.*;

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

        Stack<String> stack = new Stack<>();
        String[] strArr = s.split("");
        
        for (int i = 0; i < s.length(); i ++) {
            if (stack.isEmpty() || !stack.peek().equals(strArr[i])) {
                stack.push(strArr[i]);
            }
            else {
                stack.pop();
            }
        }

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

결과

ArrayList를 사용했을 때와 Stack을 사용했을 때 속도의 차이는 크게 나지 않았다.

회고

아직 문제를 보자마자 써야하는 자료구조나 알고리즘이 바로 떠오르지는 않는다. 이론을 좀 더 공부하고 실전에 적용하는 것을 더 연습할 필요가 있을 것 같다.