[Python/프로그래머스] 이진 변환 반복하기 - level 2

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

프로그래머스

 

 

 

 

❕ 첫 번째 풀이 (Test Case 11개 중 9개 성공)

 

왜 나는 한방에 맞추는 법이 없을까 ????????????????

효율성 테케가 있는 문제도 아닌데 2개에서 또 시간 초과가 났다.

내가 이 문제를 풀이한 로직은 아래와 같다.

 

1. Input s 에서 0을 찾아서 삭제

2. 1만 남은 s를 2진수로 변환

3. s의 길이가 1이 될 때 까지 1-2 반복

 

def solution(s):
    answer = []
    cnt=0 #이진변환 회차
    zero=0 #제거할 0의 총 개수
    
   
    while True:
        lst = list(s)
        
        if len(lst) == 1:
            break
            
        while True:
            if '0' in lst:
                lst.remove('0')
                zero += 1
            else:
                break
                
        s = str(format(len(lst), 'b'))
        cnt += 1
        print(s,zero,cnt)

    answer.append(cnt)
    answer.append(zero)
    
    return answer

처음 문제를 이렇게 풀었는데, input s 에서 0을 찾는 과정에서 for-if 문을 사용해서 0을 찾은 후에 remove로 삭제하면 index 에러가 생길 것 같아서

while문, in, del 을 사용해서 알고리즘을 짰다.

 

근데 왜 시간초과가 나는지 생각해보니 while문 안에서 if-in을 계속해서 사용하면 리스트의 모든 원소를 반복문 한번 돌 때마다 전부 검사하기 때문에 에러가 나는 것 같았다.

그래서 바꾼 코드는 아래와 같다.

 

 

❕ 두 번째 코드(성공)

def solution(s):
    answer = []
    cnt=0 #이진변환 회차
    zero=0 #제거할 0의 총 개수
    
    while True:
        if len(s) == 1:
            break
            
        temp_zero=0
        for i in range(0, len(s)):
            if s[i] == '0':
                temp_zero += 1
                zero += 1
        s_len = (len(s)-temp_zero)
        s = format(s_len, 'b')
        cnt += 1
    
    answer.append(cnt)
    answer.append(zero)
    
    return answer

그냥 s를 계속해서 갱신해줄 필요 없이, for-if 문을 이용해 0의 개수만 세고

(전체 s의 길이-0개수) 로 바로 s의 길이를 구해서 2진수로 바꾸어 주었다.

 

이렇게 하니까 시간초과도 안나고 바로 성공!

이렇게 보니 위에서 처음 짠 코드랑 시간이 엄~~~~~~~~~~청 많이 차이나네😂