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

 

문제 : 이진 변환 반복하기

바로가기

 

문제 설명

0과 1로 이루어진 어떤 문자열 x에 대한 이진 변환을 다음과 같이 정의합니다.

1. x의 모든 0을 제거합니다.
2. x의 길이를 c라고 하면, x를 "c를 2진법으로 표현한 문자열"로 바꿉니다.
예를 들어, x = "0111010"이라면, x에 이진 변환을 가하면 x = "0111010" -> "1111" -> "100" 이 됩니다.

0과 1로 이루어진 문자열 s가 매개변수로 주어집니다. s가 "1"이 될 때까지 계속해서 s에 이진 변환을 가했을 때, 이진 변환의 횟수와 변환 과정에서 제거된 모든 0의 개수를 각각 배열에 담아 return 하도록 solution 함수를 완성해주세요.

 

제한 조건

• s의 길이는 1 이상 150,000 이하입니다.
• s에는 '1'이 최소 하나 이상 포함되어 있습니다.

 

입출력 예

s	return
"110010101001"	[3,8]
"01110"	[3,3]
"1111111"	[4,1]

 

해답 및 해설

파이썬 (Python)

def solution(s):
    length = len(s)
    check_num = int(s,2)
    step_count = 0    
    del_zero_count = 0

    while check_num > 1:
        one_count = 0

        # 자리수 확인
        for i in range(length):
            # 해당 자리수가 1이면
            if check_num & (1<<i):
                one_count += 1

        del_zero_count += (length - one_count)
        check_num = one_count

        # 자릿수 체크
        length = 0
        lenght_check_num = check_num
        while lenght_check_num > 0:
            lenght_check_num = lenght_check_num>>1
            length += 1

        step_count += 1

        print(step_count, check_num, length)
        
    answer = [step_count, del_zero_count]
    return answer

print(solution(s))

이진 변환 문제라 이진 변환으로 풀려 하였으나, 그렇게 푼다고 해서 딱히 해법이 이뻐보이는건 아니었다.

 

def solution(s):
    length = len(s)
    check_num = int(s,2)
    step_count = 0    
    del_zero_count = 0
    is_first_try = True

    while check_num > 1:
        one_count = 0

        # 자리수 확인
        while check_num > 0:
            if check_num & 1:
                one_count += 1
            check_num = check_num >> 1
            if not is_first_try:
                length += 1

        del_zero_count += (length - one_count)
        check_num = one_count

        is_first_try = False
        length = 0
        
        step_count += 1
        
    answer = [step_count, del_zero_count]
    return answer

줄여본답시고 줄여보긴 했는데 또 그렇게 간단해지지는 않았다.

 

def solution(s):
    a, b = 0, 0
    while s != '1':
        a += 1
        num = s.count('1')
        b += len(s) - num
        s = bin(num)[2:]
    return [a, b]

문자열을 이용해서 간단하게 푸는 법은 다음과 같다. 심지어 이게 위 두 가지 방법보다 시간이 더 짧게 걸린다...

 

 

자바스크립트 (Javascript)