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

---

🔗 문제 링크

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

프로그래머스

---

👩‍💻 코드

// 효율성 오답!
#include <iostream>
#include <string>

using namespace std;

int solution(string s){
    int pointer = 0;
    
    while(pointer < s.size()){
        if(s[pointer] == s[pointer+1]){
            s.erase(pointer, 2);
            
            if(pointer > 0){
                pointer--;
            }
        }else{
            pointer++;
        }
    }

    return s.empty() ? 1 : 0;
}

#include <iostream>
#include <string>
#include <stack>

using namespace std;

int solution(string s){
    stack<char> letters;
    
    for (char c : s){
        if (!letters.empty() && letters.top() == c){
            letters.pop();
        } else {
            letters.push(c);
        }
    }

    return letters.empty() ? 1 : 0;
}

---

📝 풀이

첫 번째 풀이는 효율성에서 오답이 나왔다.

erase 메서드로 문자열을 지우게 되면 나머지 부분을 모두 이동시켜 시간 복잡도가 크기 때문에 비효율적이다.

 

그래서 두 번째 풀이에서는 stack을 사용하였다.

stack은 문자열의 크기에 상관없이 시간복잡도가 O(1)이기 때문에 효율적이다.

글자를 stack에 넣어 둔 뒤 top이 같은 글자인 경우 pop을 하여 stack을 비워줬다.

 

문자열을 끝까지 비교한 후 모두 짝지어 제거됐으면  stack이 비어있기 때문에 1을 return 아니면 0을 return 한다.