[파이썬] 다음 큰 숫자

programmers.co.kr/learn/courses/30/lessons/12911

코딩테스트 연습 - 다음 큰 숫자

 

문제 설명

자연수 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 이하의 자연수 입니다.

---

입출력 예

 

n	result
78	83
15	23

 

입출력 예 설명

입출력 예#1
문제 예시와 같습니다.
입출력 예#2
15(1111)의 다음 큰 숫자는 23(10111)입니다.

 

🥰 나의 풀이

 

def solution(n):
    def change(n):      #2진수로 변환
        answer=[]
        while n!=0:
            answer.append(n%2)
            n=n//2
        answer.reverse()
        num1=answer.count(1)
        return num1
        
    num=change(n)       #1의 갯수를 알아낼려고 처음 실행
    num1=0
    while num != num1:
        n+=1
        num1=change(n)
    return n

 

이제 재귀 스스로 잘 쓸 수 있다 😄

2진수로 변환하기 위해 n이 0이 될 때까지 계속 나눈다. while문이 끝난 후에 answer값을 뒤집는다. n을 2진수로 변환한 값 answer에서 1의 갯수를 세어 num1에 넣고 반환한다.

처음에 change함수를 while문에 넣고 돌리니 재귀 오류가 났다. num1이 계속 바껴서 그렇다. 2진수로 변환한 n의 1의 갯수가 고정되도록 while문 밖에 썼다. 1의 갯수가 같아지면 반복문을 빠져나오고 숫자n을 반환한다.

 

🧐 다른 사람 풀이

 

def solution(n):
    c = bin(n).count('1')
    for m in range(n+1,1000001):
        if bin(m).count('1') == c:
            return m

 

bin(n)은 integer number를 2진수 문자열로 변환한다. 나는 직접 짰는데 ㅠㅜ

c에 이진수n에서 1의 갯수를 센다. n보다 1 큰 수에서 반복을 시작한다. n이 1,000,000 이하의 자연수이므로 끝을 1000001으로 했다. 1의 갯수가 똑같으면 숫자m을 리턴한다.

이렇게 하면 재귀를 쓰지 않고도 풀 수 있구나 느꼈다.

 

def solution(n, count = 0):
    return n if bin(n).count("1") is count else solution(n+1, bin(n).count("1")if count is 0 else count)

 

1의 갯수가 count와 같으면 n을 리턴한다. 그렇지 않으면 재귀로 실행된다.

is대신에 ==를 쓰는게 권장된다. if count is 0 else count는 처음에 count가 0이기 때문에 n에서 1의 갯수를 세고 그 다음부터는 count는 바뀌지 않는다.