[프로그래머스] Level3 110 옮기기 - Greedy

문제:
https://programmers.co.kr/learn/courses/30/lessons/77886#

문제요약:
"1"과 "0"으로 이루어진 문자열에서 "110"의 위치를 옮겨 최대한 작은(사전 순서상 빨리 오게) 문자열로 만드는 문제.

문제분석:
앞쪽에는 "0"이나 "10"이, 뒤쪽에는 연속되는 "1"이 오게 해야한다.

문제풀이:
1. 우선 "110"을 전부 다 빼주고, 개수만 기록해둔다.

int cnt110 = 0;
for(int i=0; i<s.size(); ++i){
	while(i<s.size()-2 && is110(s, i)){
		cnt110++;
		s.erase(i, 3);
		i -= 2;
		if(i<0) i=0;
	}
}

그러면 연속되는 "1"은 맨뒤로 이동할 수밖에 없다.

2. "110"을 모두 없앤 문자열을 뒤에서 부터 "0"이 나올 때 까지 탐색하고, 그 자리에 "110"을 모두 넣어준다.

int i;
for(i=s.size()-1; i>=0; --i){
	if(s[i]=='0')
	break;
}
for(int j=0; j<cnt110; ++j){
	s.insert(i+1, "110");
}

전체 코드:

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

using namespace std;

bool is110(string &s, int i){
    if(s[i]=='1'&&s[i+1]=='1'&&s[i+2]=='0')
        return true;
    return false;
}

vector<string> solution(vector<string> str) {
    vector<string> answer;
    for(auto s:str){
        int cnt110 = 0;
        for(int i=0; i<s.size(); ++i){
            while(i<s.size()-2 && is110(s, i)){
                cnt110++;
                s.erase(i, 3);
                i -= 2;
                if(i<0) i=0;
            }
        }
        int i;
        for(i=s.size()-1; i>=0; --i){
            if(s[i]=='0')
                break;
        }
        for(int j=0; j<cnt110; ++j){
            s.insert(i+1, "110");
        }
        answer.push_back(s);
    }
    return answer;
}