[프로그래머스 | Java | 2017 팁스타운] 짝지어 제거하기

문제

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

프로그래머스

---

접근

처음에는 가장 직관적인 방법으로 일반 반복문을 통해서 문자열 조작을 해주려고 했는데, 몇 가지 테스트 케이스에서 실패와 시간초과가 떴다. 

 

"짝" 지어 제거하기인 문제인 만큼, 괄호 문제에서 짝지어서 제거해줬던 것처럼 자료구조 스택을 이용해야 했던 문제이다. 

 

첫번째 코드 - 일반 반복문 사용 (시간 초과)

package week15.baek.august20.baek;

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

        while(s.length() > 0){
            for (int i = 0; i < s.length()-1; i++) {
                if(s.charAt(i) == s.charAt(i+1)) {
                    if(i > 0) {
                        String result = s.substring(0, i - 1);
                        result.concat(s.substring(i + 2));
                        s = result;
                        System.out.println(s);
                    }
                }

                //끝까지 같은 문자열을 못찾았다면
                if(i == s.length() - 2) {
                    return answer;
                }
            }
        }

        //while문을 탈출 했다는 것은 모두 제거되었다는 뜻
        answer = 1;
        return answer;
    }

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

 

최종 코드 -  Stack 사용

package week15.baek.august20.baek;

import java.util.Stack;

public class P_PairRemove {
    public static int solution(String s)
    {

        Stack<Character> stack = new Stack();
        for (int i = 0; i < s.length(); i++) {
            //스택이 비어있으면 현재 위치 문자 넣어주기
            if(stack.isEmpty()) {
                stack.push(s.charAt(i));
            }

            //스택이 비어있지 않고
            else {
                //스택 맨 위와 현재 위치 문자가 같을 때 = 제거
                if(stack.peek() == s.charAt(i)) {
                    stack.pop();
                }

                //같지 않다면 스택에 현재 위치 문자 넣어주기
                else {
                    stack.push(s.charAt(i));
                }
            }
        }

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

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