프로그래머스 Level 3 110옮기기

110옮기기 (프로그래머스 Level 3)

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

프로그래머스 AI한테 dp 좀 그만달라고 하였더니
탐색과 문자열, 구현 쪽 문제를 주었다

역시 처음에는 일일이 110을 제거한 후, 특정 위치에 붙여넣는 방식으로
풀었는데 당연히도 시간초과가 발생했다

반례를 찾던 중, 보게 된 힌트에서 구현 쪽을 보강하여 통과할 수 있었다

1. ‘110’을 ‘전부’ 제거 하고, 그 개수를 세준다
   -> 110은 사실 ‘아무 곳’이나 붙일 수 있다
   따라서 110을 전부 제거하고, 남은 문자열의 임의의 위치에 전부 붙여줄 수 있다
   
2. 가장 마지막에 등장하는 0 뒤에 붙이는 것이 가장 ‘작은 수’로 만들어진다
   110을 제거하였으므로,
   10, 0 , 그 외엔 11 등의 문자열이 남아있을 것인데
   예를 들어 011 에서 0 뒤에 110을 붙여주는 것이 ‘가장 작은 수’가 만들어 진다
   011011
   

Code

#include <string>
#include <vector>
#include<math.h>

using namespace std;

bool find110(const string& s, int startInd)
{
    if (s.size() <= startInd + 2)
        return false;

    if (s[startInd] == '1' &&
        s[startInd + 1] == '1' &&
        s[startInd + 2] == '0')
        return true;

    return false;
}

bool find111(const string& s, int startInd)
{
    if (s.size() <= startInd + 2)
        return false;

    if (s[startInd] == '1' &&
        s[startInd + 1] == '1' &&
        s[startInd + 2] == '1')
        return true;

    return false;
}

string func(string s)
{
    const int sSize = s.size();
    if (sSize <= 2)
        return s;

    // 1. 110을 전부 제거하기
    int deleteCount = 0;
    string temp = s;
    int pos = 0;
    while ((pos = temp.find("110", pos)) != string::npos)
    {
        temp.erase(pos, 3);
        deleteCount++;
        pos = max(pos - 3,0);
    }

    // 2. 삽입을 할 위치 찾기
    int lastZeroPos = 0;
    for (int i = 0; i < temp.size(); i++)
    {
        if (temp[i] == '0')
        {
            lastZeroPos = i + 1;
        }
    }

    string temp2 = temp.substr(0, lastZeroPos);
    string temp3 = temp.substr(lastZeroPos, temp.size() - lastZeroPos);

    for (int i = 0; i < deleteCount; i++)
    {
        temp2 += "110";
    }

    return temp2 + temp3;
}

vector<string> solution(vector<string> s) {
    vector<string> answer;
    for (auto str : s)
    {
        answer.push_back(func(str));
    }

    return answer;
}