25. 이진 변환 반복하기 Lv.2 : 월간 코드 챌린지 시즌 1

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

프로그래머스

* 코드

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

using namespace std;

vector<int> solution(string s) {
    vector<int> answer;
    int count = 0;
    int sum_c = 0;

    while (s != "1") {
        // '0' 제거
        int pre_size = s.size();
        s.erase(remove(s.begin(), s.end(), '0'), s.end());
        int post_size = s.size();

        // 제거된 '0'의 개수
        sum_c += pre_size - post_size;

        // 이진 변환
        string binary = "";
        while (post_size > 0) {
            binary = to_string(post_size % 2) + binary; // 이진수 생성
            post_size /= 2; // 2로 나누기
        }

        s = binary; // 새로운 이진수 문자열로 업데이트
        count++;
    }

    answer.push_back(count);
    answer.push_back(sum_c);

    return answer;
}

 

*해설

이 문제는 두 단계로 나눠져 있다.

1. 문자열의 '0'을 전부 제거한다.

2. 그 문자열의 길이를 이진변환을 통해 새로운 문자열로 만든다.

이제 이것을 반복하며 문자열의 길이가 1이 될때까지 반복하면 된다.

 

문자열의 '0'을 제거하는 것은 간단하다. erase()함수를 이용해 제거하면된다.

 

그럼 이제 이진변환을 구현하도록 하자.

10진수를 2진수로 변환하는 방법을 하면된다.

이렇게 하듯이 2로 나눴을때의 나머지 값이 가장 오른쪽에 오게되고 원래 값을 2로 나눈 것을 다시 2로 나눈 나머지를 구하면서 2진수변환을 시킬 수가 있다.

그렇게 구한 int형을 to_string()으로 변환시켜주면서 새로운문자열을 만들고 이를 반복하면 쉽게 풀 수 있다.