2017 팁스타운 짝지어 제거하기

본 풀이는 java 언어를 사용하였습니다.
문제 보러가기

풀이

처음에는 문자열을 하나씩 순회하면서 이전 알파벳과 현재 알파벳을 비교해서 같으면 문자열을 제거하는 식으로 구현했는데, 코드를 제출하니 효율성 체크까지 있어서 시간 초과가 났다..
고민하다가 생각이 안나서 힌트를 참조했는데 Stack 을 이용하면 된다는 글을 보았다.
처음에는 while 문으로 문자열이 모두 사라질 때까지 순회하면서 체크를 했었는데,
Stack 을 이용하니까 for 문 한번으로 끝나는거 보고 넘나 어이없었음..

방법은 간단하다.
맨처음 Stack 에 알파벳을 넣고,
문자열의 알파벳을 하나씩 체크하면서 맨 나중에 Stack 으로 들어간 값이랑 비교 (peek) 하면서
만약 값이 같다면 Stack 에 들어가 있는 알파벳을 제거한다.
for 문을 한바퀴만 돌면 끝나는 이유를 설명하면 아래와 같다.

s = "baabaa" 일 때,
1 ) 현재 값 : b, 스택 : (b PUSH) [b]
2 ) 현재 값 : a, 스택 : (b PUSH) [b, a]
3 ) 현재 값 : a, 스택 : (a POP) [b]
4 ) 현재 값 : b, 스택 : (b POP) []
5 ) 현재 값 : a, 스택 : (a PUSH) [a]
6 ) 현재 값 : a, 스택 : (a POP) []

위처럼 for 문 한번으로 모든 알파벳이 제거될 수 있기 때문에 효율성이 좋아진다. (O(n))

코드

import java.util.Stack;

public class Solution {

    private static final int TEXT_ALL_CLEAR = 1;
    private static final int NO_TARGET_REMOVED = 0;

    public int solution(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char alphabet = s.charAt(i);
            if (!stack.isEmpty() && stack.peek() == alphabet) {
                stack.pop();
                continue;
            }
            stack.push(alphabet);
        }
        return stack.isEmpty() ? TEXT_ALL_CLEAR : NO_TARGET_REMOVED;
    }
}

회고

문제를 보고 Stack 을 떠올렸다면 정말 쉽게 풀었을 텐데 while 문으로 지저분한 코드를 만들면서 효율성에서 떨어지니 약간 현타가 옴..
어떤 자료구조를 써야하는지 바로바로 알기가 쉽지 않은 것 같다. 계속 연습하면 감이 오겠지..?