문제 11) 짝지어 제거하기

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

프로그래머스

---

알파벳 소문자로 구성된 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 짝을 찾은 다음에는 그 둘을 제거한 뒤 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성하세요. 성공적으로 수행할 수 있으면 1을, 아니면 0을 반환해주면 됩니다. 예를 들어 문자열 S가 baabaa라면

• baabaa -> bbaa -> aa

순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다.

 

제약조건

• 문자열의 길이 : 1,000,000 이하의 자연수
• 문자열은 모두 소문자로 이루어짐

입출력의 예

s	result
"baabaa"	1
"cdcd"	0

---

아이디어

처음에는 이중 for문을 사용하려 했으나, 시간복잡도가 초과될 것 같아 다른 방법을 고려했다. 스택을 사용하면 간단하게 해결할 수 있었다.

초기에 스택에 문자를 집어넣고, 이전 글자와 겹치지 않는다면 push, 겹친다면 이전 글자를 pop 하며 문자열을 검색해나가면 간단하게 해결 가능하다. 

 

나중에도 이런 문제에 조건을 잘 확인해서 이중 for문 대신 스택을 사용하여 해결할 수 있도록 해야겠다.

private static int solution(String s){
        Stack<Character> stack = new Stack<>();

        for(int i=0; i<s.length(); i++){
            char c = s.charAt(i);
            if(stack.isEmpty() || stack.peek() != c){
                stack.push(c);
            }
            else{
                stack.pop();
            }
        }

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