[프로그래머스] 이진 변환 반복하기 with C++

문제 설명

---

제한 사항 및 입출력 예제

---

개념

　1과 0으로 구성된 문자열에서 특정 조건을 만족할 때까지 이진 변환 프로세스를 반복하는 문제다. 프로세스는 다음과 같다.

1. 문자열에서 0을 제거 (제거한 횟수 카운트)
2. 문자열의 길이를 이진법으로 표현 (입력 문자열이 1이 될때까지, 횟수 카운트)

 

　이때 문자열의 길이를 이진법으로 표현하기 위해 bitset 라이브러리를 사용하면 효율적으로 문제를 풀 수 있다.

---

풀이

#include <vector>
#include <algorithm>
#include <bitset>
using namespace std;

vector<int> solution(string s)
{
    vector<int> answer(2);
    int cnt = 0;
    
    while (s[0] != '1' || s.size() != 1)
    {
        int num = count(s.begin(), s.end(), '1');
        int num_of_zero = s.size() - num;
        answer[1] += num_of_zero;
        s.clear();

        bitset<32> b(num);
        s = b.to_string();
        s.erase(0, s.find_first_not_of('0'));
        cnt++;
    }
    
    answer[0] += cnt;

    return answer;
}

　해당 코드는 문자열에 있는 1의 개수를 count() 함수로 계산한다. 문자열의 전체 길이에서 이 1의 개수를 빼면, 제거해야 하는 0의 개수를 알 수 있다. 정답 벡터 answer는 [변한 횟수, 제거한 0의 개수]로 구성되므로, answer[1]에 0의 개수를 더한다. 그 후, 입력 문자열 s를 비운다.

　그 다음, 문자열의 길이가 1의 개수와 동일하므로, 이를 이진 변환한다. 이때 bitset은 이진 변환 결과의 앞부분을 0으로 채우므로, 이 부분을 erase() 함수로 제거해준다. 이 프로세스를 1이 단 하나만 남을 때까지 반복하게 해주면 문제를 해결할 수 있다.