[프로그래머스][Java] Lv.2 짝지어 제거하기

---

문제 분석

 

연속된 문자를 짝을 지어 제거한다.

문자열 길이가 1,000,000이하로 길이가 길다.

 

위 조건을 보고  Stack을 사용해야 한다는 것을 알아차려야 한다.

(필자는 ArrayList로 풀려다가 망했다..)

---

풀이과정

 

1. for문으로 문자열을 처음부터 끝까지 검사한다.
2. 스택이 비어있다면 문자를 넣고 다음 반복문을 실행한다.
3. 스택이 비어있지 않다면 제일 위의 문자와 현재 넣으려는 문자가 같은지 확인한다.
4. 같은 문자라면 pop을 사용해 해당 문자와 현재 넣으려는 문자를 제거한다.
5. 같은 문자가 아니라면 그냥 push 해준다.
6. 문자열 검사를 다 끝내고, stack이 비어있다면 짝지어 모든 문자를 제거했다는 뜻으로 answer=1을 리턴한다.
7. 반면에 stack이 비어있지 않다면 문자를 더이상 제거할 수 없기 때문에 answer=0을 리턴한다.

---

전체 코드

import java.util.Stack;
class Solution
{
    public int solution(String s)
    {
        int answer = 1;

        //주어진 s의 길이가 홀수라면 무슨 짓을 하던 마지막에 1개가 남는다.
        if(s.length()%2==1) return 0;
        
        Stack<Character> stack = new Stack<>();
        
        for(int i=0;i<s.length();i++){
            //stack 비어있으면 검사할 필요없이 문자 넣음.
            if(stack.isEmpty()){
                stack.push(s.charAt(i));
                continue;
            }
            //stack의 제일 위의 문자와 넣을 문자가 같다면 pop
            if(stack.peek()==s.charAt(i))
                stack.pop();
            //같은 문자가 아니라면 push해줌.
            else
                stack.push(s.charAt(i));
        }
        if(!stack.isEmpty())
            answer=0;
        
        return answer;
    }
}