2023-04-16 이진 변환 반복하기

Summary

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

생각한 부분

s 의 최대 길이 150,000 에 대하여 이진 변환을 한다고 가정하였다. 길이 150,000 에서 모든 수가 1이었다고 가정하더라도 다음 변환된 숫자의 길이는 20을 넘기지 않는다 (2^20 은 약 1,000,000) 따라서 변환 과정에서 1의 수를 셀 때 완전 탐색을 이용하여 문제 없이 해결 할 수 있다.

해결한 방법

문제의 조건 그대로 1단계, 2단계에 거쳐 변환하는 과정을 반복한다.

  • 문자열 s 가 ‘1’ 이 될 떄까지
    1. 문자열 s 를 1의 개수만큼 concat 한 문자열로 재할당 (문자열 s 에서 0을 제거하는 과정)
    2. 1단계에서 변환후 반환된 문자열 s의 길이를 2진수로 변환하여 문자열 s 에 재할당
    3. 이 과정에서 제거된 0의 갯수와 변환 횟수를 ans 리스트에 기록
1
2
3
4
5
6
7
8
9
10
11
12
13
14

def solution(s):
    """
    [110010101001 -> 111111 -> 110]
    [110 -> 11 -> 10]
    [10 -> 1 -> 1]
    """
    ans = [0, 0]
    while s != '1':
        one_length = s.count('1')
        ans[1] += len(s) - one_length
        s = bin(one_length)[2:]
        ans[0] += 1

    return ans

comments powered by Disqus