프로그래머스 Lv2 문제입니다. 실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.

문제

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

[나의 풀이]

⌛ 시간 초과 (일부 케이스 시간 초과 80/100)

def get_bin(x):

    x = bin(x)[2:]
    
    return x

def solution(numbers):
    answer = []
    
    for num in numbers:

        bigger =  num+1
        num = get_bin(num)
        find = False
        
        while not find:
            
            diff = 0
            bigger_bin = get_bin(bigger)               
            
            if len(bigger_bin)>len(num):
                num = '0'*(len(bigger_bin)-len(num)) + num
      
            for x1,x2 in zip(num,bigger_bin):
                if x1!=x2:
                    diff += 1
                if diff>=3:
                    break
                           
            if diff<=2:
                answer.append(bigger)
                break

            bigger += 1
            
    return answer

입력된 숫자 배열(numbers)이 주어질 때, 각 숫자별(num)로 큰 수들 중 이진법으로 변환했을 때 다른 숫자가 2개 이하인 최소값을 구하는 문제입니다.🐓🐓🐓

각 숫자들과 해당 숫자보다 큰 수들 bin()함수를 이진화하고 문자열 하나마다 각각 비교하여 답을 도출하였지만 2개 케이스에서 시간초과가 발생하였습니다.

현재 풀이 보다 더 빠른 알고리즘으로 개선하기 어렵다고 판단하여 다른 풀이를 참고 하였습니다.

[다른 사람의 풀이1]

def get_bin(x):
    x = bin(x)[2:]
    
    return x

def solution(numbers):
    answer = []
    
    for num in numbers:
    
        if num%2==0:
            num = get_bin(num)
            num = num[:-1] + '1'
            answer.append(int(num,2))
            
        else:
            num = get_bin(num)
            num = '0'+num
            idx = num.rindex('0')
            num = num[:idx]+'10'+num[idx+2:]
            answer.append(int(num,2))
    
    return answer

입력된 숫자들(numbers)에서 각 숫자별로 짝수인지 or 홀수인지 분류하여 해결하는 알고리즘입니다.🐣🐣🐣

만약 숫자(num)가 짝수라면 이를 이진화하였을 때, 맨 마지막 문자는 반드시 0입니다. 이때, +1연산만 한다면 맨 마지막문자가 1로 바뀌고 요구한 조건과 같이 1~2 문자만 다른 현재 숫자(num)보다 큰 수가 됩니다.

만약 홀수라면 숫자를 이진화한 문자열에서 0인 인덱스 중 가장 우측에 위치하면 인덱스(idx)를 찾아 1로 바꾸고, 그 왼쪽 수를 0으로 바꾼다면 정확히 2개 문자열만 다르고 현재 숫자(num)보다는 큰 최소값을 구할 수 있었습니다.

[다른 사람의 풀이2]

def convert_odd(temp):
    ls_temp = list(temp[::-1])
    idx = 0
    for i in ls_temp:
        if i == '1':
            idx += 1
        else :
            break

    ls_temp[idx] = '1'
    ls_temp[idx-1] = '0'
    return int(''.join(ls_temp)[::-1], 2)

def solution(numbers):
    answer=[]
    for number in numbers:
        if number % 2 == 0:
            answer.append(number+1)
        else:
            temp = format(number, 'b')
            if '0' not in temp:
                temp = '0' + temp
            temp = convert_odd(temp)
            answer.append(temp)
    return answer

'다른 사람의 풀이1'과 같이 짝수 or 홀수 구분을 통한 알고리즘입니다.🦘🦘🦘

약간 다른 점은 숫자를 이진화할 때

format(10, 'b')
# 1010

로 표현하여, '나의 풀이'처럼 bin()함수 적용 후 슬라이싱([2:]) 없이 사용할 수 있다는 점이 달랐습니다.

감사합니다.