[프로그래머스LV2 : 짝지어 제거하기]

문제 설명

문제 설명
짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다.

🤔 처음 코드 및 생각

class Solution
{
    public int solution(String s)
    {
        int answer = 0;
        while(true){
            //종료조건
            if(s.length() == 0){
                answer = 1;
                break;
            }
            
            //반복되는 거 지우기
            int isChange = 0;
            for(int i = 0; i < s.length()-1; i++){
                if(s.charAt(i) == s.charAt(i+1)){
                    s = s.substring(0, i) + s.substring(i+2);
                    isChange = 1;
                }
                
                if(i == s.length()-2 && isChange == 0){
                    return 0;
                }
            }
            
        }
        return answer;
    }
}

---

문자열에 최대 100만까지의 길이니까 for문을 한 번만 사용하면 상관없을 것 같았는데 너무 짧게 생각했다..그 안에서도 계속 while 되니까 사실상 어마어마하게 비효율적으로 돌아가는 형태!

효율성 테스트는 모조리 실패하는 괴랄한 코드를 작성해버렸다..
효율도 안 좋은데 substring까지 막 쓰니 다른 방법을 생각해야했다.
정렬을 하고 같은 것들을 삭제하는 방식도 생각했는데 그럼 애초에 막 섞여버린다..우리가 원하는 것은 처음에 주어진 것에서 삭제하는 방식이니까

---

두 번째로 생각한 방법인데 이것도 별로 좋은 방법은 아니다..
사실 하면서도 아닐거라는 생각은 들었는데 속도가 확실히 늘었나 궁금해서 해봤다!

class Solution
{
    public int solution(String s)
    {
        int answer = 0;
        for(int i = 0; i < s.length()-1; i++){
            if(s.charAt(i) == s.charAt(i+1)){
                s = s.substring(0, i) + s.substring(i+2);
                
                if(i > 0){//지금  i = 2 cbaabaa -> cbbaa -> caa
                    if(s.charAt(i-1) == s.charAt(i)){
                        s = s.substring(0, i-1) + s.substring(i+3);
                        i = i - 1;
                    }
                }
            }
        }
        
        if(s.length() == 0){
            answer = 1;
        }
        return answer;
    }
}

---

정답

가장 좋은 방법은 스택이었다. 스택은 자동으로 선입선출이기 때문에 가장 최근에 올려두었던 것이 peek되면서 우리가 원하는 방식으로 삭제하기 수월하다!

import java.util.*;

class Solution{
    public int solution(String s){
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
			char ch = s.charAt(i);
			if(!stack.isEmpty() && stack.peek() == ch)
                stack.pop();
			else stack.push(ch);
		}

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