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

문제

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

프로그래머스

문제 요약

x의 모든 0을 제거하고 그 길이를 c라고 한다면, c를 2진법으로 표현한다.

이게 이진 변환이라고 한다면, 주어진 s를 가지고 1이 될때까지 위 방식을 반복한다. 

---

풀이

이진 변환 방식을 코드로 나타내고 1이 될때까지 반복되도록 while문을 작성하면 금방 푸는 문제였다. 

bin() 함수를 활용해서 쉽게 이진수로 나타내면 더 빠르게 풀 수 있다.

def solution(s):
    cnt = 0
    zero = 0

    while s != '1':
        zero += s.count('0')
        s = s.replace('0', '')
        s = bin(len(s))[2:]
        cnt += 1

    return [cnt, zero]

 

시간복잡도

0의 개수를 세고 삭제하고 변환하고 <- 하면 길이 자체가 N logn... log log n이기 때문에 다 합하면 O(n) 정도 된다.