[알고리즘 문제 풀이] - 이진 변환 반복하기

 

오늘은 프로그래머스에서 이진 변환 트리를 풀어보았습니다.

 

주어진 숫자는 오직 0과 1로만 이루어져 있고 먼저 0을 모두 제거합니다.

 

그 후에 남은 1이 몇개인지 세고 1의 개수를 다시 이진법으로 변환합니다.

 

이 작업을 마지막 1이 남을때까지 반복하는 해야 되네요.

 

그리고 마지막에 0의 개수와 총 몇번이나 이 과정을 거쳤는지 list 안에 넣어서 리턴하면 됩니다.

 

 

<생각의 과정>

1. 0을 제거하고 남은 1의 개수를 이진법으로 변환하는 과정을 몇번이나 해야 되는지 알수 없다.

 

2. 그러므로 첫 loop은 while loop으로 (1이 되면 loop이 깨지는 구조)

 

3. 안에 또 다른 loop이 필요한가? 그렇다 1의 개수를 세야 한다

 

4. 굳이 0을 제거할 필요가 있는가? 아니다 1의 개수만 세서 이진법으로 변환한 숫자가 다시 loop으로 들어간다

 

 

<풀이>

def solution(s):
    transform, zero_count = 0, 0

    while s != '1':
        zero_count += s.count('0')
        one_count = s.count('1')
        s = bin(one_count)[2:]
        transform += 1
        
    return [transform, zero_count]

 

안에 for loop을 돌려서 0의 숫자를 세고 1의 숫자를 세도 되지만

 

파이썬에 있는 count()라는 function을 사용하였습니다. 

 

시간복잡도는 for loop을 돌리는것과 차이가 없지만 

 

코드를 볼때 count를 쓰는게 좀 더 심플하고 보기 편하기 때문에 count를 썼습니다.

 

저는 여기서 bin()이라는 function을 써서 2진법으로 변환 시킨후에 slice 했습니다.

 

그 이유는 bin()을 쓰고 난 후의 output은 앞에 '0b'가 붙기 때문입니다.

 

'0b'를 제외시키기 위해 slice를 썼습니다.

 

그래서 결과는...

 

 

효율성 테스트는 따로 없었네요.

 

통과된 시간을 봐서는 10번 테스트 케이스가

 

효율성까지 테스트하는 케이스 같습니다.

 

굉장히 큰 숫자가 아닐까 예상해 봅니다.

 

채점 후에 다른 분들의 답을 다들 알고리즘은 비슷하네요.