Programmers - 다음 큰 숫자

프로그래머스

 

 

문제

 

자연수 n이 주어졌을 때, n의 다음 큰 숫자는 다음과 같이 정의 합니다.

조건 1. n의 다음 큰 숫자는 n보다 큰 자연수 입니다.
조건 2. n의 다음 큰 숫자와 n은 2진수로 변환했을 때 1의 갯수가 같습니다.
조건 3. n의 다음 큰 숫자는 조건 1, 2를 만족하는 수 중 가장 작은 수 입니다.
예를 들어서 78(1001110)의 다음 큰 숫자는 83(1010011)입니다.

자연수 n이 매개변수로 주어질 때, n의 다음 큰 숫자를 return 하는 solution 함수를 완성해주세요.

제한 사항
- n은 1,000,000 이하의 자연수 입니다.

 

 

접근방식

10진수를 2진수로 어떻게하면 변환할 수 있는지 먼저 생각해봄

n이 15일 때 2진수로 표현하면 1111인데, 우선 n이 1이 될 때 까지 2로 계속 나눠줌

n == 1 이 되기 전까지 나머지를 저장하고 1이 됐을 때 몫을 저장한 후, 거꾸로 출력하면 2진수로 표현 가능함

 

문제에서는 n보다 큰데, n을 2진수로 표현했을 때의 1의 개수와 같은 1의 개수를 가지는 가장 작은 수를 찾고 있음

따라서 몫은 저장할 필요 없이(마지막 n == 1 이 될 때는 모든 수가 몫을 1을 가지므로) 나머지들 중 1의 개수가 같은 수를 찾으면 됨

 

 

코드

def solution(n):
    answer = 0
    arr = []
    ans_arr = []
    n_score = 0
    m = n + 1
    while n != 1:
        tmp = n % 2
        if tmp == 1:
            n_score += 1
        arr.append(tmp)
        n = n // 2
    
    while m != 1:
        tmp = m % 2
        if tmp == 1:
            answer += 1
        ans_arr.append(tmp)
        m = m // 2
        if m == 1 and n_score == sum(ans_arr):
            break
        elif m == 1 and n_score != sum(ans_arr):
            m += 1
    
    return m

원래 코드를 이렇게 작성했는데 시간 초과가 뜸

while 루프를 두 번 사용하여 모든 수를 확인하고 비교하려고 해서 연산량이 기하급수적으로 많아져서 그런 것 같음

 

숫자를 2진수로 표현할 때 쓰는 함수가 같으므로 저렇게 while 문을 두 번 쓰는게 아니라 함수로 선언해서 사용하는 방법을 생각해냈음

그리고 주어진 숫자에 대해 2진수로 변환하면서 나머지가 1일 때의 개수를 세서 변수에 저장하고 n 값을 더해주면서 나머지가 1일 때의 개수가 같은 수가 있으면 바로 반환해줌

 

 

수정 코드

def countOneBit(num):
    cnt = 0
    while num != 1:
        tmp = num % 2
        if tmp == 1:
            cnt += 1
        num = num // 2
    return cnt

def solution(n):
    count_n = countOneBit(n)
    
    while True:
        n += 1
        if count_n == countOneBit(n):
            return n

이렇게 푸니까 깔끔하게 통과함

풀이를 찾아보니,  파이썬 내장 함수 중에 10진수를 2진수로 변환해주는 함수(bin)가 있음을 알게 되었음

 

def check(x):
    binary = bin(x)
    one = binary.count('1')
    return one  

def solution(n):
    answer = n
    num = check(n)
    while True:
        answer += 1
        if int(check(answer)) == num:
            return answer