프로그래머스 (짝지어 제거하기, 2017 팁스타운) C++

 

Stack의 개념을 사용하게 되는 경우를 배울 수 있었던 문제이다.

현재의 것과 이전의 것을 비교하고 erase 하게 되는 경우 stack을 사용하면 효율성 측면에서 훨씬 빠르게 접근이 가능하다는 것을 배웠다.

 

#include <iostream>
#include <string>
#include <stack>
using namespace std;

int solution(string s)
{
    int answer = -1;
    stack<char> st;
    
    // 문자열의 길이만큼 검사를 한다.
    for(int i = 0 ; i < s.size() ; i++) {
        // stack이 비어있거나 문자열의 현재 문자와 top이 같지 않다면 push를 한다.
        if(st.empty() || st.top() != s[i]) 
            st.push(s[i]);
        // top과 현재 문자가 같다면 제거시킨다.
        else if(st.top() == s[i])
            st.pop();
    }
    
    if(st.empty()) return 1;
    else return 0;
    
}

 

 

다음은 효율성 문제에서 다 시간 초과가 걸렸던 내 풀이

 

#include <iostream>
#include<string>
using namespace std;

int solution(string s)
{
    int answer = -1;
    int len = s.size();

    for(int i =0 ; i < len - 1  ; i++) {
        if(s[i] == s[i+1]) {
            s.erase(i,2);
            if(i != 0)
                i = i - 2;
            else if(i == 0)
                i = i - 1;
        }
        
        if(s.size() == 0) {
            answer = 1;
            break;
        }
    }
    
    if(s.size() != 0) return 0;
    else return answer;
}