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

<문제 소개>

---

<소스 코드>

#include <string>
#include <vector>

using namespace std;

vector<int> solution(string s) 
{
    vector<int> answer;  
    
    int num = 0; // 반복 횟수
    int count = 0; // 제거된 0의 갯수
    
    while(s != "1")
    {        
        num++;
        
        // 모든 0 제거
        string x;
        for(int i = 0; i < s.size(); i++)
        {
            if(s[i] == '1') x += s[i];
            else count++; // 제거된 0의 갯수 카운팅
        }
        
        // 길이를 2진법으로 표현
        int c = x.size();
        
        string bin, next_s;
        
        while(c > 0)
        {
            bin += ((c % 2) + '0'); // 역순으로 저장됨
            c /= 2;
        }
        
        // 역순 -> 원래 순서대로 변경
        for(int i = bin.size() - 1; i >= 0 ; i--)
        {
            next_s += bin[i];
        }
                
        s = next_s; // 다음 s에 대입
    }
    
    answer.push_back(num);
    answer.push_back(count);
    
    return answer;
}

---

<풀이과정>

1. 반복횟수와 제거된 0의 갯수를 담을 변수를 각각 선언(num, count)

2. 주어진 문자열 s가 "1"이 아닌 동안, 즉 s가 "1"이 될때까지 반복을 진행

3. 매 반복마다 num은 1씩 증가함

4. 이진 변환의 첫번째 과정으로 주어진 문자열에서 모든 0을 제거하기위해 먼저 제거된 문자열을 나타낼 x를 선언.

5. 문자열 s의 원소들을 돌면서 '1'인 경우에는 x에 추가하고, 아닌 경우에는 제거된 0의 갯수 count를 증가시킨다.

6. 두번째 과정은 앞서 구한 0을 제거한 문자열 x의 길이를 2진법으로 표현해야함.

7. 문자열 x의 길이를 c로 선언하고, c를 2진법으로 바꿀때 바뀐 2진법을 나타내는 수를 표현하기 위한 문자열 bin과 next_s를 선언함.

8. 소인수분해 과정을 이용해 c를 2로 나눈 나머지를 문자로 바꾸어 bin에 추가하고, c를 2로 나눈다. 이 과정을 c가 0보다 큰 동안, 즉 c가 0보다 같거나 작아질 때까지 반복을 진행함.

9. 위의 과정에서는 문자열의 특성상 뒤로만 추가가되는 구조이므로 bin은 역순으로 저장되게 된다.

10. 따라서 bin을 뒤집어서 next_s에 저장해주는 과정을 거치고, 뒤집은 수 next_s는 s에 저장하여 다음 반복을 진행할 수 있게 한다.

11. s가 1이되어 모든 반복이 끝난 경우, answer에 반복된 횟수 num을 추가하고, 제거된 0의 갯수 count도 추가해 준 뒤 리턴한다.

---

<코멘트>

처음에 매번 제거되는 0의 갯수들을 벡터에 담아 리턴해주는 문제인줄 알았는데 아니었다..ㅋㅋㅋ

귀찮다고 대충 읽지 말고 문제 좀 제대로 읽자!!

---

<제출결과>