Programmers - 이진 변환 반복하기

---

title: Programmers - 이진 변환 반복하기
date: 2022-07-11
tags:

• Algorithm

---

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

문제 요약

0과 1로 이루어진 문자열이 주어진다. 0을 모두 제거하고, 남은 1로만 구성한 문자열의 길이를 다시 2진수로 표시한다.
이것이 이진 변환이며, 주어진 문자열이 1이 될 때까지 이진 변환을 반복한다.
이진 변환 횟수, 그리고 제거한 0의 개수를 vector에 넣어 return한다.

문제 풀이

우선 문자열의 길이는 최대 150k이다. 1s를 기준으로 잡으면 O(nlogn) 까지 허용이 되나, O(n)이면 해결 가능하다고 생각하였다.
첫 이진 변환을 할 때, 남은 1의 개수는 최대 150k이다. 이 값이 아닌, 길이를 이용하므로 문자열의 길이가 17개 이하로 줄어드는 것이다.
0과 1인지 확인만 하면 되므로 문제의 관건은 두 가지이다. 첫 문자열에서 0을 제거하는 과정, 그리고 남은 작은 문자열을 처리하는 방법이다.

어차피 길이를 세는 것이므로, 문자열을 편집할 이유는 없다. 첫 문자열은 1의 개수를 세기만 하면 되는 것이다.
이후 나온 값은 문자열로 변환하는 것 보다, 그 개수를 이용하여 비트 연산을 하는 것이 훨씬 빠르다.
프로그램이 문자열 처리, 이후 나온 값을 이용한 처리 두 부분으로 나누어진다. 좋은 프로그램이 아닐 수 있으나, 효율성을 생각하면 충분히 감안할 수 있다.
문자열 처리를 통해 나온 값은 비트 연산, 비트 shift 1회 반복을 진행한다.
해당 반복 횟수가 1번이라면 더 이상 연산을 할 필요가 없고, 이외의 경우에는 0의 개수를 세면서 계속 더해주기만 하면 된다.

프로그램

#include <string>
#include <vector>

using std :: vector ;
using std :: string ;

vector < int > solution ( string s )
{
    vector < int > answer ( 2 , 0 ) ;
    int iCnt = 0 ;
    int iSize = s.size () ;
    const char * cpTemp = s.data () ;
    int iTarget = 0 ;



    for ( int i = 0 ; i < iSize ; ++i )
    {
        if ( '1' == cpTemp [ i ] )
            ++ iCnt ;
    }
    if ( 0 == iCnt )
    {
        return answer ;
    }

    ++ answer [ 0 ] ;
    answer [ 1 ] += iSize - iCnt ;
    iTarget = iCnt ;

    while ( true )
    {
        iCnt = 0 ;
        iSize = 0 ;

        while ( 0 != iTarget )
        {
            if ( 1 & iTarget )
                ++ iCnt ;

            iTarget >>= 1 ;
            ++ iSize ;
        }
        if ( 1 == iSize )
            return answer ;

        ++ answer [ 0 ] ;
        answer [ 1 ] += iSize - iCnt ;
        iTarget = iCnt ;
    }


    return answer ;
}