[Python] 연습문제 : 다음 큰 숫자

정확도 테스트에서는 통과했는데 효율성에서 실패했었다

문제를 풀다가 첫번째 커다란 벽을 부딪힌 느낌이였다

시간복잡도를 줄여야한다고 하는데 ...

 

이진수로 바꾸는 함수를 몰라서 직접 구현을 해서 그런 것 같다.

이진수로 바꾸는 부분을 bin함수를 이용하는 것으로 바꿨더니 통과했다!

코테 문제를 풀 때는 유용한 함수들을 알고 있는 것도 필요한 부분 같다.

 

 

 

---

 

 

 

 

문제

 

---

문제 설명

 

n이 주어졌을 때, n의 다음 큰 숫자를 return 하는 함수를 만들어라

 

n의 다음 큰 숫자의 조건

• 조건 1. n의 다음 큰 숫자는 n보다 큰 자연수
• 조건 2. n의 다음 큰 숫자와 n은 2진수로 변환했을 때 1의 갯수가 같습니다.
• 조건 3. n의 다음 큰 숫자는 조건 1, 2를 만족하는 수 중 가장 작은 수 입니다.

 

예시 

1. 78(1001110) => 83(1010011)
2. 15(1111) => 23(10111)

 

---

 

코드

통과한 코드

# n을 이진수로 변화한 후에 
# n의 이진수와 
# n의 다음 큰 숫자의 이진수의 1의 갯수가 같으면서 
# n보다 큰 수를 return 해라.

def change_two(n):
    change_n = bin(n)[2:]
    return change_n



def solution(n):
    
    change_n = change_two(n)
    
    cncnt = change_n.count("1")
    cbncnt = 0
   
    while cncnt != cbncnt:
    # n보다 큰 수를 이진수에 계속 값을 넣어보고 1의 개수가 같은지 비교한다.
        n += 1
        change_big_n = change_two(n)
        cbncnt = change_big_n.count("1")
    
    
    # print('n', n)
    big_n = n
    
    
    answer = big_n
    return answer

 

 

 

 

 

 

 

효율성 테스트 실패 뜬 코드

change_two 함수만 달라짐

def change_two(n):
    i = 0
    # n에 2의 i승 한 것을 나눴을 때 1보다 클 동안 (=작을 경우 그 값으로 나눠지지 않는 것이다.)
    while n / (2 ** i) >= 1:
        i+=1

    # 이진수로 바꾸기 위해 리스트를 생성한다.
    change_n = ["0"] * i

    # i번 for문을 반복한다. (i-1부터 0까지의 -1씩 줄면서 k에 값이 들어가게 됨)
    while n != 0:
        for k in range(i-1, -1, -1):  
            # n이 2의 k승보다 크거나 같을 경우 해당 자리를 1로 바꿔주고 
            # n에 2의 k승 값을 빼준다.
            condition = 2**k
            if n >= condition:
                change_n[k] = "1"
                n -= condition
            

    change_n = change_n[::-1]
    change_n = "".join(change_n)
    return change_n

 

 

 

---