프로그래머스 문제 - 110 옮기기

프로그래머스 110 옮기기 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

0과 1로 이루어진 문자열을 문자열에 있는 "110"을 뽑아 임의의 위치에 다시 삽입하는 행동을 통해 최대한 사전 순으로 앞에 오도록 만들고자 합니다.
각 문자열에 대해서 만들 수 있는 문자열 중 사전 순으로 가장 앞에 오는 문자열을 만들어야합니다.

문제 풀이

사전 순으로 가장 앞에 있는 문자열은 0과 1로 이루어진 문자열을 2진수로 표현이 되었을 때 가장 작은 수를 의미합니다.
다른 느낌으로 생각하면 숫자 0들을 문자열의 맨 앞으로 보낼수록 더 사전 순으로 가까운 문자열이 됩니다.
즉 0이 최대한 문자열 앞으로 가도록 정렬하는 문제입니다.
stack을 사용하여 문제를 해결할 수도 있겠지만, 충분히 문자열들만 이용하여 문제를 해결할 수 있습니다.

"11000"에서 "110"을 뺄 경우 "10"과 "110"이 되는 것처럼 "110"을 빼면 주어진 문자열이 바뀌게 됩니다.
즉 "110"을 빼면 보이지 않던 "110"문자열이 또 생성될 수 있습니다.
예를 들면 "11111000"을 한 번 빼주면 "11100", "110"이 되어 문자열에서 "110"을 한번 더 뽑을 수 있게 됩니다.
0을 최대한 앞으로 보내주어야 하기 때문에 문자열에 보이는 "110"을 전부 뽑아줘야 합니다.

이후에 0을 최대한 앞으로 보내주고 1들을 뒤로 보내주어야 합니다.
"110"에도 0이 존재함으로 최대한 문자열의 앞으로 보내주어야 사전 순으로 가까운 문자열을 만들 수 있습니다.
그러므로 뽑은 "110"문자열들을 뽑고 남은 문자열의 맨 뒤에 있는 0뒤로 나열하게 된다면 사전 순으로 가장 앞에 오는 문자열을 만들어 낼 수 있습니다.
만약 뽑고 남은 문자열에 0이 존재하지 않는다면 "110"문자열들을 전부 앞으로 붙여주면 사전 순으로 가까운 문자열을 만들 수 있습니다.

전체 코드

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

vector<string> solution(vector<string> s) {
    vector<string> answer;
    
    for(int i = 0; i < s.size(); i++)
    {
        string curString = s[i];
        int oneCount = 0;
        int strCount = 0;
        int zeroIndex = -1;
        //110을 제외한 문자열을 저장해줌
        string result = "";
        //110을 찾아주며 뽑고 남은 문자열들과 뒤의 1의 갯수를 저장해줌
        for(int j = 0; j < curString.size(); j++)
        {
            if(curString[j] == '1')
            {
                oneCount++;
            }
            else
            {
                if(oneCount >= 2)
                {
                    oneCount -= 2;
                    strCount++;
                }
                else
                {
                    zeroIndex = j;
                    if(oneCount == 1)
                    {
                        result += "1";
                    }
                    oneCount = 0;                   
                    result += curString[j];
                }
            }
        }
        string temp = "";
        //110수만큼 110문자열을 나열하여 만듬
        while(strCount--)
        {
            temp += "110";
        }
        //110을 뺀 문자열에 0이 없는 경우
        if(zeroIndex == -1)
        {
            while(oneCount--)
            {
                result += "1";
            }
            result = temp + result;
        }
        else //110을 뺀 문자열에 0이 있는 경우 0 뒤에 110문자열을 삽입해줌
        {
            result = result + temp;
            while(oneCount--)   //1갯수만큼 맨 뒤에 추가
            {
                result = result + "1";
            }
        }
        
        answer.push_back(result);
    }
    
    return answer;
}

출처

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