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

이진 변환 반복하기

문제 링크

이진 변환 반복하기

분석

문자열의 모든 0을 제거하고, 길이(크기)를 2진법으로 표현한 문자열로 바꿉니다.
이 과정을 문자열의 길이가 1이 될때까지 반복합니다.

제거를 반복한 횟수와 제거된 0의 개수를 반환합니다.

풀이

#include <string>
#include <vector>

using namespace std;

vector<int> solution(string s) {
    vector<int> answer(2);
    
    // s가 1일 때까지 반복
    while (1 < s.length())
    {
        // s에서 0의 개수
        int zeroCount = 0;
        // s에서 1만 분리한 문자열
        string substr;
        
        // s 순회
        for (int i = 0; i < s.length(); ++i)
        {
            // s에서 1을 분리해서 저장하고, 0은 개수만 샌다
            if (s[i] == '1')
            {
                substr += s[i];
            }
            else
            {
                ++zeroCount;
            }
        }
        
        // 분리한 문자열의 크기
        int strSize = substr.length();
        // 2진수를 저장하기 위해 기본 값으로 초기화
        s = "";
        
        // 2진수 생성
        while (strSize != 0)
        {
            s += (strSize % 2 == 1) ? '1' : '0';
            
            strSize /= 2;
        }
        
        // 반복한 횟수 추가
        ++answer[0];
        // 0의 개수 저장
        answer[1] += zeroCount;
    }
    
    return answer;
}

성능 요약

시간 복잡도는 $O(n log n)$입니다.

• s가 "1"만 남을 때까지 반복하는 반복문 $O(log n)$
• s에서 "0"을 제거하는 반복문 $O(n)$
• s의 크기를 이진수로 변환 $O(log n)$
• $O(n log n + log^2 n)$

공간 복잡도는 $O(n)$입니다.

• "1"을 분리한 문자열 substr $O(n)$
• 이진수로 변환한 문자열 s$O(log n)$
• $O(n + log n)$

테스트 1 〉 통과 (0.01ms, 4.19MB)
테스트 2 〉 통과 (0.18ms, 4.19MB)
테스트 3 〉 통과 (0.01ms, 4.06MB)
테스트 4 〉 통과 (0.01ms, 4.13MB)
테스트 5 〉 통과 (0.01ms, 4.2MB)
테스트 6 〉 통과 (0.01ms, 4.06MB)
테스트 7 〉 통과 (0.02ms, 4.19MB)
테스트 8 〉 통과 (0.02ms, 4.2MB)
테스트 9 〉 통과 (0.38ms, 4.13MB)
테스트 10 〉 통과 (0.82ms, 4.19MB)
테스트 11 〉 통과 (0.28ms, 3.84MB)