프로그래머스/이진 변환 반복하기

 

 0과 1로 이루어진 문자열의 길이가 1이 될 때까지 제시된 조건에 따라 줄여나가면 되는 단순한 문제다. 조건의 모든 과정을 적용시켜서 구현해보았다.

 

---

▽ '이진 변환 반복하기' 문제 첫번째 제출 코드

 

#include <string>
#include <vector>

using namespace std;

string to_string_binary(int length)
{
    string temp = "";

    if (1 < length)
        temp += to_string_binary((length - length % 2) / 2);

    if (0 == length % 2)
        temp += "0";
    else if (1 == length % 2)
        temp += "1";

    return temp;
}

vector<int> solution(string s)
{
    vector<int> answer = { 0,0 };

    while ("1" != s)
    {
        answer[0]++;
        
        for (int i = 0; i < s.length(); i++)
        {
            if ('0' == s[i])
            {
                answer[1]++;
                s.erase(s.begin() + i--);
            }
        }

        s = to_string_binary(s.length());
    }

    return answer;
}

 

 정말 단순하게 쓰여진대로 string에서 0을 뺐다가, 문자열의 길이를 이진수 문자열로 교체했다가, 다시 검사해서 0을 빼고하며 반복시켰다. 단순한 문제라서 통과는 했지만 속도가 최고 188ms가 나왔다. 좀 더 고민해서 개선이 가능한 부분들을 개선해서 다시 제출했다.

 

---

▽ '이진 변환 반복하기' 문제 두번째 제출 코드

#include <string>
#include <vector>

using namespace std;

int changer(int length, int& answer)
{
    int count = 0;

    while (0 < length)
    {
        if (1 == length % 2)
        {
            length--;
            count++;
        }
        else
        {
            answer++;
        }

        length /= 2;
    }

    return count;
}

vector<int> solution(string s)
{
    vector<int> answer = { 0, 0 };
    
    if ("1" == s)
        return answer;

    answer[0]++;

    for (int i = 0; i < s.length(); i++)
    {
        if ('0' == s[i])
            answer[1]++;
    }

    int count = s.length() - answer[1];

    while (1 != count)
    {
        answer[0]++;
        count = changer(count, answer[1]);
    }

    return answer;
}

 

 처음에 string이 주어지긴 하지만, 사실 계속 string으로 작업을 할 이유는 없었다. 처음 문자열에서 '1'과 '0'의 갯수만 구하고 0의 갯수는 결과값에 더하기로, 1의 갯수는 다시 2진수로 전환시키는 함수에 집어넣었다.

 2진수로 전환시킬 때에도 어차피 0은 제거해야할 대상이기 때문에 결과값만 증가시켜주었고 1의 갯수만 새서 리턴, 리턴 값이 1이 아니라면 다시 함수를 반복시켰다.

 불필요한 연산을 많이 없앴기 때문에 최고 0.5ms의 좋은 결과가 나왔다.