짝지어 제거하기 (JAVA)

프로그래머스_짝지어 제거하기

처음 풀이

처음 이 문제를 시도하였을 때는 StringBuilder로 문자열을 받아서 같은 문자가 나오면 해당 인덱스들을 지워버리고 하는 쌩쇼를 했다.

사실 이 풀이도 방식으로만 보면 맞다. 하지만 한 문자를 지우면 그 문자열을 다시 처음부터 탐색하고 같은 행동을 반복하다보니 정말 긴 문자열의 경우 거의 무한루프와 다름없는 코드가 되었고 그 결과 런타임에러와 시간초과등의 문제가 발생하였다.

초기 코드 및 결과

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

        StringBuilder builder = new StringBuilder();
        builder.append(s); //builder에 s 넣기
        int i = 0;
        while(true){
            char front = builder.charAt(i);
            char back = builder.charAt(i+1);
            if(front == back){
                builder.deleteCharAt(i+1);
                builder.deleteCharAt(i);
                if(builder.length()==0){
                    answer = 1;
                    break;
                }
                i = 0;
                continue;
            }
            i++;
            if(i == builder.length()-1){
                answer = 0;
                break;
            }
            if(builder.length()%2==1){
                break;
            }
        }
        return answer;
    }
}

최종 풀이

도저히 모르겠어서 구글링을 잠깐 해보았다. 대부분의 사람들은 스택을 이용해서 푼 것을 보았다. 생각해보니 한 글자씩 넣고 만약 같은 문자가 연속해서 나온다면 빼내면 된다. 이 전에 크레인 인형뽑기때도 스택을 이용하면 더 쉬웠었다.
그 때도 스택을 안쓰고 배열로 겨우겨우 풀긴 했지만 결국 다 비슷한 유형의 문제였다.

스택 큐 리스트 등을 알기만하면 아무소용없다. 적절할 때 해당 기본 자료형들도 잘 사용하는 법을 익혀야겠다.

최종 코드 및 결과

import java.util.Stack;

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

        Stack <Character> stack = new Stack<>();
        char []arr = s.toCharArray();

        for(int i = 0;i<arr.length;i++){
            if(stack.empty()){
                stack.push(arr[i]);
                continue;
            }

            if(stack.peek() == arr[i])
                stack.pop();
            else{
                stack.push(arr[i]);    
            }
        }

        if(stack.empty())
            answer = 1;

        return answer;
    }
}