[프로그래머스 lv2] 이진 변환 반복하기 풀이

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

해설

 

s가 1이 되기 전까지 이진 변환을 반복하면서 반복횟수와 0의 제거 횟수를 카운트하는 문제이다.

 

간단하게 생각하면, 이진 변환은 결국 s에 있는 1을 개수를 세어 해당 수를 이진수로 나타내는 것이다.

s를 순환하며 1의 개수를 카운트하고, 0이 될 때까지 2로 나누어 이진 변환을 수행한다.

이진수의 총 길이에서 1의 개수를 뺀 값이 곧 제거된 0의 개수이므로 이를 기록하여 추후에 제거된 총 0의 개수를 함께 리턴할 수 있도록 한다.

 

 

코드

 

#include <cstdio>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

int change(string& s) {

    int cnt = 0;
    for (auto x : s)
        if (x == '1') cnt++; //1 카운트
    int ret = s.size()-cnt; //제거한 0의 개수 리턴

    string tmp = "";
    while (cnt) {
        tmp = to_string(cnt%2) + tmp;
        cnt /= 2;
    }
    s = tmp;

    return ret;
}

vector<int> solution(string s) {

    int t = 0;
    int cnt = 0;
    while (s != "1") {
        cnt += change(s); //이진변환
        t++;
    }
    return {t, cnt};
}