프로그래머스 - 110 옮기기 [C++]

이 문제는 스택, 문자열을 이용한 그리디로 풀었다.

처음에는 이 문제에 kmp 알고리즘을 적용해봤다. 일부 테스트 케이스는 맞췄으나, 나머지에서 시간 초과가 났다.

다른 방법을 찾을 수 없어 검색을 통해 그리디 알고리즘을 사용한다는 사실을 발견했다.

 

만약 "110" 을 제외한 나머지 부분에 0이 하나도 없다면, 앞에 "110" 들을 나란히 붙여주는 것이 가장 숫자가 작다. 0이 하나라도 있다면 마지막 0 뒤에 110을 채워 넣어야 그 뒤에 있는 1들이 뒤로 밀려나면서 숫자가 작아지게 된다. 이를 그대로 구현하면 시간 초과 없이 정답이 나온다.

#include <string>
#include <vector>
#include <algorithm>
#include <stack>

using namespace std;

int findLastZero(string str)
{
    int result = -1;
    int size = str.size();
    for (int i = 0; i < size; i++)
    {
        if (str[i] == '0')
        {
            result = i;
        }
    }
    return result;
}

string substring(string rest, int lastZero)
{
    string result = "";
    for (int i = 0; i <= lastZero; i++)
    {
        result += rest[i];
    }
    return result;
}

string convert(string number)
{
    stack<char> st;
    string zero = "011";
    
    int size = number.size();
    
    int numberOf110 = 0;
    
    for (int i = 0; i < size; i++)
    {
        char c = number[i];
        
        st.push(c);
        
        if (st.size() >= 3 && st.top() == '0')
        {
            int index = 0;
            vector<char> temp;
            bool flag = false;
            
            while (st.top() == zero[index])
            {
                temp.push_back(st.top());
                st.pop();
                index++;
                
                if (index == 3)
                {
                    flag = true;
                    break;
                }
            }
            
            if (flag)
            {
                numberOf110++;
            }
            else
            {
                for (int i = temp.size() - 1; i >= 0; i--)
                {
                    st.push(temp[i]);
                }
            }
        }
    }
    
    string rest = "";
    while (!st.empty())
    {
        rest += st.top();
        st.pop();
    }
    
    reverse(rest.begin(), rest.end());
    
    string result = "";
    
    int zeroIndex = findLastZero(rest);
    
    if (zeroIndex == -1)
    {
        for (int i = 0; i < numberOf110; i++) 
        {
            result += "110";
        }
        
        result += rest;
    }
    else
    {
        int index = zeroIndex;
        
        string substr = substring(rest, index);
        
        result += substr;
        for (int i = 0; i < numberOf110; i++)
        {
            result += "110";
        }
        for (int i = substr.size(); i < rest.size(); i++)
        {
            result += rest[i];
        }
    }
    
    return result;
}

vector<string> solution(vector<string> s) 
{
    vector<string> answer;
    
    for (string number : s)
    {
        answer.push_back(convert(number));
    }
    
    return answer;
}