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

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

프로그래머스

  입력 문자열이 들어오면 "짝지어 제거하기" 가 가능한 지 확인하면 된다.

짝지어 제거하기란, 문자열 중 같은 알파벳이 2개 붙어있으면 그 pair 를 제거하는 것이며

이를 반복하여 문자열을 날려버릴 수 있다면 짝지어 제거할 수 있는 문자열인 것이다.

 

  가장 처음에 떠오른 풀이는, 문자열을 순회하면서 짝지어 제거할 수 있는 pair 가 발견되면

substr 을 이용해서 문자열을 줄여나가다가 문자열이 비게 되면 짝지어 제거할 수 있는 문자열 인 것이고

문자열이 남아있다면 짝지어 제거할 수 없는 문자열으로 판단하는 것이다.

 

  하지만 해당 문제에서 입력으로 주어지는 문자열의 최대 길이는 1,000,000 이며 위 방법으로 풀이하는 경우 반복문을 계속 돌아야 하기 떄문에 TLE 가 발생한다. 그러므로 보다 효율적으로 풀이하는 방법이 필요하다.

문자열을 순회하면서 STACK 에 각각의 알파벳을 넣고, 직전에 들어온 문자와 현재 스택의 TOP 을 비교하여 짝지어 제거핡 수 있는지 판단하는 방법으로 풀이할 경우 O(N) 으로 풀이가 가능하다.

 

풀이 1.

[C++]

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

using namespace std;

bool check(string& s)
{
    string u = ""; string v = "";
    for(int i = 1 ; i < s.size(); i ++)
    {
        if(s[i-1] == s[i])
        {
            u = s.substr(0, i-1);
            v = s.substr(i+1, s.size()-1);
            s = u + v;
            return true;
        }
    }
    return false;
}

int solution(string s)
{
    int answer = 0;
    while(!s.empty())
    {
        if(check(s)) continue;
        else
        {
            return 0;
        }
    }
    
    return 1;
}

 

풀이2

[C++]

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

using namespace std;

int solution(string s)
{
    int answer = 0;
    stack<char> st;
    for(int i = 0 ; i < s.size(); i ++)
    {
        st.push(s[i]);
        if(st.size() < 2) continue;
        else
        {
            char top_element = st.top();
            st.pop();
            
            if(st.top() == top_element) 
            {
                st.pop();
            }
            else
            {
                st.push(top_element);
            }
            
        }
    }
    if(st.empty() == true) answer = 1;
    else 
    {
        answer = 0;
        while(st.empty()) st.pop();
    }
    
    return answer;
}