[C++] 이진 변환 반복하기 - 2진법 형태 문자열 만들기

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

나의 풀이

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

using namespace std;

vector<int> solution(string s) {
    vector<int> answer;
    vector<string> str;
    int count = 0; // 전체 루트 반복 수
    int count_zero = 0; // 제거할 0의 개수
    
    // 자동 길이 조절이 가능한 vector str에 옮겨 담음
    for (int i = 0; i < s.size(); i++) {
        str.push_back(s[i]);
    }
    
    while (true) {
        for (int i = 0; i < str.size(); i++) {
            if (str[i] == "0") {
                str[i] = "";
                count_zero++;
            }
        }
        
        int p = str.size();
        int div_num = 0; // 2진수의 자릿수
        while (p) {
            p = p / 2;
            div_num++;
        }
        int str_length = str.size();
        string cal_2div = "";
        for (int i = 0; i < div_num; i++) {
            if (str_length % 2 == 0) {
                cal_2div += "0";
            } else cal_2div += "1";
        }
        
        for (int i = 0; i < cal_2div.size(); i++) {
            str.push_back(cal_2div[i]);
        }
        count++;
        
        if (str.size() == 1) { // 이진 변환 결과 s의 길이가 1이면 while문 종료
            break;
        } else continue;
    }
    answer.push_back(count);
    answer.push_back(count_zero);
    
    return answer;
}

실패 요인 분석:

• 테스트 케이스를 따라가면서 1회만큼의 코드를 구현하고 while 문으로 반복해서 최종적으로 s가 "1"이 되면 반복문이 끝나도록 구성했다. 아무래도 while 문을 2번 쓰고, for문과 if문이 많아서 시간이 많이 카운팅된 것 같다.

• 테스트 케이스를 확인할 수도 없었고, 코드를 간략화해야할 수 밖에 없었다. 다음은 다른 사람의 풀이를 분석한다.

#include <string>
#include <vector>
#include <iostream>
using namespace std;

vector<int> solution(string s) {
    vector<int> answer(2);// answer[0] : 몇번 턴이 돌았는지, answer[1]:제거된 0의 개수
    string temp;
    int length =0;
    while(1){
        if(s.size()==1) break;
        for(int i=0; i<s.size(); i++){
            if(s[i]=='0') { 
                answer[1]++;//제거된 0의 개수 증가시키기
                continue;
            }
            else length++;
        }
        s.clear();
        for(int i=length; i>0; i=i/2){
            s.push_back(i%2+'0');
        }
        length =0;

        answer[0]++; //한 턴이 돌았다는 의미
    }
    return answer;
}

분석:

• answer 벡터는 2개의 원소로 이루어지므로 추가적인 int형 변수 선언 및 push_back() 없이 한 번에 ++; 로 증가시킨다.

• while (1)로 시작한 것은 동일하다. 이 부분은 나도 간략화하기 힘든 부분이라고 봤다.

• while (1)로 시작한 만큼 반복 종료 조건이 필요했고, 내가 구현한 것과 동일하게 s.size()가 1이면 종료하도록 구성되어 있다.

• s의 원소를 하나씩 볼때 0이 보일때마다 answer[1]을 1씩 증가시켰다. 여기서 중요하면서 나와의 차이점은 answer[1]만을 제어하고, 실제 s에서 0을 뺀다거나 하는 불필요한 코드가 없다는 것이다. (너무 테스트 케이스 순서를 그대로 따라간 내 잘못이다. 작은 아이디어 하나씩 줄여가며 메모리/시간 단축을 꾀하자.)

• s.clear()로 기존에 있던 2진수를 초기화하고, 다음 반복문에서 이진 문자열을 생성한다.

이진 문자열 생성하기

for(int i = length; i > 0; i = i / 2){
        s.push_back(i % 2 + '0');
}

1. 이진수로 만드려는 수는 length에 해당한다. 0보다 커질때까지 2로 반복해서 나누어 반복문을 구성한다.
2. i % 2 + '0' 기억하자. 'a & 1' 기억나는가. 이는 홀수인지 검사하는 비트 연산 기법이다. 이와 마찬가지로 보면 된다. 여기서 i % 2인 나머지가 0이면 결과는 ASCII의 값 '0'이 되고, 나머지가 1이면 결과는 ASCII 값 '1'이 된다.
3. 문자열 s에 넣기 위해 이렇게 구현되었고, 이 방법을 이용하면 내가 사용한 불필요한 while 문을 쓰지 않아도 된다.

• length를 다시 0으로 초기화하고, 반복 1회 당 answer[0]++로 횟수를 1 추가한다.