[프로그래머스] 이진 변환 반복하기 + Python 변수 할당 최적화

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

프로그래머스

문제 설명

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

x의 모든 0을 제거합니다.
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'이 최소 하나 이상 포함되어 있습니다.

---

문제 해결을 위한 로직 생각하기

문자열에서 0 제거
→ 제거한 0의 개수를 더하기
→ 남은 1의 개수를 2진법으로 만들어 문자열에 저장
→ 이진 변환 횟수 더하기
→ 문자열이 1이 되면 결과를 리턴

 

 

# 초기 코드
def dec_to_bin(s,bin=""):
    if s==0: return bin
    return dec_to_bin(s//2,bin=str(s%2)+bin)

def solution(s):
    del_sum = 0
    count = 0
    while True:
        new_s = s.replace("0","")
        del_sum += len(s)-len(new_s)
        new_s = dec_to_bin(len(new_s))
        count+=1
        if new_s == "1": break
        s = new_s
    answer = [count,del_sum]
    return answer
# 2.02ms

 

복습할 겸 재귀함수로 2진법으로 변환하는 함수를 만들고

위에 쓴 로직대로 코드를 구현했다. 역시 처음 코드는 러프하게 쓰게된다.

그냥 직관적으로 코드를 작성하다보니..

 

개선할만한 아이디어를 생각해보면,

replace 대신 count를 사용?

직접 만든 함수 말고 내장함수 bin() 사용하기

while문에 break 조건을 직접 넣기

 

 

1차 수정 : 가독성 개선

# 1차 수정 : 가독성 개선
def solution(s):
    del_sum = 0
    count = 0
    while s != '1':
        one_count = s.count('1')
        del_sum += len(s) - one_count
        s = bin(one_count).lstrip('0b')
        count+=1
    return [count,del_sum]
# 0.59ms

 

가독성을 개선했는데 성능도 훨씬 좋아졌다.

내장함수 bin()을 사용하고, len() 사용량이 줄어서 그런듯?

근데 이것저것 추가로 해보다가 코드는 더 길어지는데 속도가 빨라지는 것을 경험했다.

 

 

2차 수정 : 변수 할당

# 2차 수정 : 변수 할당
def solution(s):
    del_sum = 0
    count = 0
    while s != '1':
        len_s = len(s)
        one_count = s.count('1')
        zero_count = len_s - one_count
        del_sum += zero_count
        s = bin(one_count).lstrip('0b')
        count+=1
    return [count,del_sum]
# 0.50ms

 

분명 코드는 2줄 더 길어졌는데 20%정도 시간이 줄었다. 이미 짧은 코드라

큰 영향은 없을 것 같지만, 중요한건 '왜 줄었냐' 이다.

 

Python을 처음 배울때 특징은 코드를 컴파일러/인터프리터에 넣으면서 최적화를 하고

한줄한줄 읽는 방식이라고 배웠다.

 

여기서 지금까지는 한줄한줄 읽는 방식이기때문에 줄이 적을수록 빠르다고 생각했었는데

컴파일러/인터프리터에 넣으면서 최적화를 하는것을 생각 안하고 있었다.

 

깊게 공부하지는 못했지만, 변수할당같은 간단한 연산은 최적화 대상이 되기 때문에

1차 수정코드보다 2차 수정코드가 최적화를 더 잘 수용하는 코드가 된 것이다.

 

공부하면 할수록 모르는게 많아진다..... 그래도 계속 파고들면 지식이 조금 더 깊어지겠지