프로그래머스: 이진 변환 반복하기

programmers70129_1 programmers70129_2

binary string에서 0 제거 후의 길이를 다시 이진수로 변환해 string이 1이 될 때까지 반복하는 횟수를 구하는 문제이다.

월간 코드 챌린지에 나왔던 문제인데 그 당시에는 십진수->이진수, 이진수->십진수로 변환하는 함수를 직접 구현했다. 이번에는 지난번에 배운 bitset을 활용해 보았는데 음.. 크게 나아지진 않은 것 같다..ㅎㅎ

지난 번 코드

#include <iostream>
#include <string>
#include <vector>
#include <cmath> // pow
#include <algorithm> // reverse
using namespace std;

int countZeros(string s) {
	int cnt = 0;
	int size = s.size();
	for (int i = 0; i < size; i++) {
		if (s[i] == '0') cnt++;
	}
	return cnt;
}

string len2bin(int len) { // len을 bin으로
	string bin = "";
	int rmd;

	while (len != 0) {
		rmd = len % 2;
		len /= 2;
		bin.append(to_string(rmd));
	}
	reverse(bin.begin(), bin.end());
	return bin;
}

vector<int> solution(string s) {
	vector<int> answer;

	int converted = 0; // 이진 변환 횟수
	int zeros = 0; // 삭제한 0의 개수

	int tmp = countZeros(s);
	while (s != "1") {
		converted++;

		// 0 지우기
		int newLen = s.size() - tmp; // 0을 제거한 string의 길이
		zeros += tmp;

		// string의 길이를 이진수로 변환
		// 다시 이진 변환한 string을 저장
		s = len2bin(newLen);
		tmp = countZeros(s);
	}

	answer.push_back(converted);
	answer.push_back(zeros);
	return answer;
}

다시 풀었을 때의 코드

#include <string>
#include <vector>
#include <algorithm> // erase
#include <bitset>
#include <cmath> // pow
using namespace std;

vector<int> solution(string s) {
    vector<int> answer;
    int zeros = 0;
    int steps = 0;
    int i;
    
    while(s != "1") {
        steps++;
        // 1. str에서 0 제거
        int beforeSize = s.size();
        s.erase(remove(s.begin(), s.end(), '0'), s.end());
        
        int afterSize = s.size();
        int diff = beforeSize - afterSize;
        zeros += beforeSize - afterSize; // string이 줄어든 길이만큼 0의 개수에 더해주기
        
        if(s == "1") break;
        
        // 2. 문자열의 길이를 이진수로 변환
        // 2-1. 문자열의 길이 구하기
        // 현재 문자열의 길이는 afterSize이다. 2^17 < 150,000 < 2^18이므로 bitset의 길이를 18로 설정하고 0 제거
        bitset<18> len(afterSize); // 문자열의 길이를 이진수로 변환. 
        s = len.to_string();
        int trim = s.find_first_of('1'); // string이 1로 시작하도록 앞의 0들은 잘라내기
        s.erase(0, trim);
        int t = static_cast<int>(pow(2, s.size())) - 1; // 이진수로 변환한 길이를 십진수로 변환
        
        // 2-2. 구한 문자열의 길이(십진수)를 이진수로 변환
        bitset<18> binlen(static_cast<int>(t));
        trim = s.find_first_of('1');
        s.erase(0, trim);
    }
    
    answer.push_back(steps);
    answer.push_back(zeros);
    return answer;
}

Share on: