[프로그래머스][LV.2] 다음 큰 숫자

[프로그래머스][LV.2] 다음 큰 숫자 | python3

2025. 2. 6. 19:56ㆍ프로그래머스/LV.2

문제 설명

문제 설명

자연수 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보다 큰 수 중 이진법으로 바꾸었을때 n의 이진수와 1의 갯수가 같은 수 중 가장 작은 수를 구하는 문제이다.

처음에 bin()함수를 사용할까하다가 앞에 부가적인 것도 붙고 해서 그냥 수를 이진법으로 바꾸었을때 1의 개수를 세어주는 함수를 만들었다.

n을 2로 나누면서 나머지가 1이되면 1씩 변수에 더한다. 맨 마지막 몫 1(이진수 맨 앞의 1)을 더해줘야 하기 때문에 변수는 1부터 시작한다.

함수를 이용하여 n의 이진수의 1의 갯수를 세서 변수에 넣어준다. 그리고 while문을 통해 1씩 더해주며 n의 이진수 갯수와 비교하여 answer값을 구한다.

내코드

def bin_one(n):
    chk=1
    if n==1:
        return 1
    while n>1:
        if n%2:
            chk+=1
        n//=2
    return chk

def solution(n):
    answer = n+1
    n_one=bin_one(n)
    while n_one!=bin_one(answer):
        answer+=1
    return answer

다른사람풀이

def nextBigNumber(n):
    num1 = bin(n).count('1')
    while True:
        n = n + 1
        if num1 == bin(n).count('1'):
            break
    return n

bin도 count 사용이 가능하구나....

♠ 속도차이

1. bin_one(n) 함수의 성능 차이

첫 번째 코드 (solution)에서 bin_one(n) 함수는 n을 2로 나누면서 1의 개수를 세는 방식입니다.
즉, **O(log n)**의 시간 복잡도를 가집니다.

이 함수는 solution에서 while 루프 안에서 계속 호출되므로 성능에 영향을 미칩니다.

2. bin(n).count('1')의 성능

반면, 두 번째 코드 (nextBigNumber)는 bin(n).count('1')를 사용하여 1의 개수를 구합니다.

bin(n): 숫자를 이진 문자열로 변환하는데 **O(log n)**의 시간이 걸립니다.
.count('1'): 변환된 문자열에서 '1'의 개수를 세는데 **O(log n)**의 시간이 걸립니다.

즉, 이진 변환 + 카운팅까지 포함해도 O(log n) 정도의 성능입니다.

3. 전체 반복문에서의 차이

첫 번째 코드 (solution)에서는 bin_one(answer)를 호출하는데, 이 함수는 O(log n)입니다.
즉, while 루프에서 매번 O(log n) 연산이 필요합니다.

반면, 두 번째 코드 (nextBigNumber)에서는 bin(n).count('1')을 사용하여 단순한 문자열 연산으로 1의 개수를 구합니다.
즉, 첫 번째 코드보다 비교적 연산량이 적습니다.

결론

첫 번째 코드(solution): bin_one(n)이 O(log n)이므로 전체적으로 O(log n * k) (k는 while 루프의 반복 횟수)
두 번째 코드(nextBigNumber): bin(n).count('1')을 사용하여 O(log n * k), 하지만 연산이 간결하여 더 빠름

=> 속도도 더 빠르다고 한다.

def nextBigNumber(n):
    answer = 0
    int2bin = "{0:b}".format(n)
    count = int2bin.count('1')

    if count == len(int2bin):
        answer = '0'+int2bin
        return int(answer,2)

    if count - 1 == len(int2bin):
        for i in range(0, count):
            answer = answer + '1'
        return int('0' + answer,2)

    r_int2char = int2bin[::-1]
    index = 0
    flag = 0
    if r_int2char[0:1] == '0':
        for i in range(1, len(int2bin)):
            if index != 0:
                break
            if r_int2char[i:].find('1') == 0:
                flag = 1
            if r_int2char[i:].find('0') == 0 and flag == 1:
                index = i
    else:
        for i in range(0, len(int2bin)):
            if index != 0:
                break
            if r_int2char[i:].find('0') == 0:
                index = i

    realIndex = len(int2bin) - index -1 
    answer = int2bin[0:realIndex]
    answer = answer + '1'
    rCount = count - answer.count('1')

    banswer = ''
    for i in range(0,rCount):
        banswer = banswer + '1'

    for i in range(0, len(int2bin)):
        if (len(answer) + len(banswer)) == len(int2bin):

            return int(answer + banswer,2)
        else:
            banswer = '0' + banswer

    return answer

1. 2진수 변환 및 1의 개수 세기

int2bin = "{0:b}".format(n)  # n을 2진수 문자열로 변환
count = int2bin.count('1')   # 2진수에서 1의 개수를 셈

n을 이진수 문자열로 변환합니다.
변환된 이진수에서 '1'의 개수를 세어 변수 count에 저장합니다.

2. 예외 처리: 모든 비트가 1일 경우

if count == len(int2bin):
    answer = '0' + int2bin
    return int(answer, 2)

만약 n의 이진수 표현이 모두 1로만 이루어져 있다면, n보다 큰 숫자 중 가장 작은 값은 10...00 (맨 앞에 1을 추가하고 나머지는 0)입니다.
예를 들어 111(7)의 경우, 가장 가까운 큰 수는 1000(8)이 됩니다.

3. 예외 처리: count - 1 == len(int2bin) 경우

if count - 1 == len(int2bin):
    for i in range(0, count):
        answer = answer + '1'
    return int('0' + answer,2)

이 조건은 절대 성립할 수 없습니다. count - 1 == len(int2bin)이 될 경우, 1의 개수가 전체 길이보다 하나 적어야 하는데, 이는 불가능한 상황입니다. (예를 들어 1111(15)는 count=4, len(int2bin)=4이며 count-1=3이므로 성립하지 않음)
불필요한 코드라고 볼 수 있습니다.

4. 오른쪽에서부터 0을 찾아 1과 스왑하는 과정

r_int2char = int2bin[::-1]  # 문자열을 뒤집음 (오른쪽부터 찾기 위함)
index = 0
flag = 0
if r_int2char[0:1] == '0':  # 맨 끝이 0일 경우
    for i in range(1, len(int2bin)):
        if index != 0:
            break
        if r_int2char[i:].find('1') == 0:
            flag = 1
        if r_int2char[i:].find('0') == 0 and flag == 1:
            index = i
else:  # 맨 끝이 1일 경우
    for i in range(0, len(int2bin)):
        if index != 0:
            break
        if r_int2char[i:].find('0') == 0:
            index = i

뒤에서부터 0을 찾고, 1과 교체할 위치를 결정하는 과정입니다.
하지만 r_int2char[i:].find('1') == 0 등의 방식은 비효율적입니다.
단순히 n의 2진수를 오른쪽에서부터 탐색해 처음 등장하는 01을 10으로 바꾸면 되는 문제입니다.

5. 1의 개수를 유지하면서 작은 자리부터 채우기

realIndex = len(int2bin) - index - 1 
answer = int2bin[0:realIndex]
answer = answer + '1'
rCount = count - answer.count('1')

banswer = ''
for i in range(0, rCount):
    banswer = banswer + '1'

for i in range(0, len(int2bin)):
    if (len(answer) + len(banswer)) == len(int2bin):
        return int(answer + banswer, 2)
    else:
        banswer = '0' + banswer

realIndex를 통해 1을 변경할 위치를 찾습니다.
앞부분(answer)과 나머지 1을 채우는 부분(banswer)을 조합해 새로운 숫자를 만듭니다.

6. 코드 개선

이 코드를 더 간결하고 효율적으로 만들 수 있습니다.

개선된 코드

python

복사편집

def nextBigNumber(n): count = bin(n).count('1') # 1의 개수 구하기 while True: n += 1 # 다음 숫자 확인 if bin(n).count('1') == count: # 1의 개수가 같다면 반환 return n

def nextBigNumber(n):
    count = bin(n).count('1')  # 1의 개수 구하기
    while True:
        n += 1  # 다음 숫자 확인
        if bin(n).count('1') == count:  # 1의 개수가 같다면 반환
            return n

개선된 코드의 장점

가독성 향상: 원래 코드보다 훨씬 간결하고 직관적입니다.
버그 수정: 원본 코드에는 불필요한 예외 처리 및 논리 오류가 있었지만, 이 방식은 직접적인 반복문을 사용하여 문제를 해결합니다.
이해하기 쉬움: 주어진 수 n보다 크면서 1의 개수가 같은 가장 작은 숫자를 찾는 문제이므로, 단순히 n+1부터 검사하는 것이 직관적입니다.

코드가 안읽혀서 gpt한테 부탁함. 읽으면 배울 점이 많은 것 같다.

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

1. 함수 정의 및 기본 매개변수 설정

def nextBigNumber(n, count=0):

n: 현재 탐색 중인 숫자
count: n의 이진수에서 1의 개수를 저장하는 변수 (초기값 0)

2. 재귀 조건

return n if bin(n).count("1") is count else ...

현재 n의 2진수에서 1의 개수가 count와 같다면 n을 반환합니다.
즉, count와 같은 1의 개수를 가진 n을 찾으면 종료됩니다.

3. 다음 숫자로 재귀 호출

nextBigNumber(n+1, bin(n).count("1") if count is 0 else count)

count == 0인 경우:
- 첫 번째 호출에서 count가 0이므로 bin(n).count("1")로 n의 1의 개수를 계산하여 count에 저장합니다.
count != 0인 경우:
- 이미 count 값이 설정되어 있으므로 유지합니다.
그런 다음 n+1을 넣고 재귀 호출하여 1의 개수가 같은 가장 작은 n을 찾을 때까지 반복합니다.

4. 예제 실행

예제 1: n = 78

bin(78) = '0b1001110' → 1의 개수 = 4
nextBigNumber(79, 4) 호출
- bin(79) = '0b1001111' → 1의 개수 = 5 (다름)
nextBigNumber(80, 4) 호출
- bin(80) = '0b1010000' → 1의 개수 = 2 (다름)
nextBigNumber(81, 4) 호출
- bin(81) = '0b1010001' → 1의 개수 = 3 (다름)
nextBigNumber(82, 4) 호출
- bin(82) = '0b1010010' → 1의 개수 = 3 (다름)
nextBigNumber(83, 4) 호출
- bin(83) = '0b1010011' → 1의 개수 = 4 (같음) → 반환

출력: 83

5. 개선할 점

is 대신 ==을 사용해야 합니다.is는 객체 비교(메모리 주소 비교)이고, count는 정수이므로 ==을 사용하는 것이 맞습니다.

return n if bin(n).count("1") == count else nextBigNumber(n+1, bin(n).count("1") if count == 0 else count)

재귀 호출이 많아질 경우 스택 오버플로우 위험이 있습니다. 대신 while 루프를 사용하면 반복 호출 없이 해결할 수 있습니다.

def nextBigNumber(n):
    count = bin(n).count("1")
    while True:
        n += 1
        if bin(n).count("1") == count:
            return n

6. 요약

재귀를 이용한 방식으로 n보다 크면서 1의 개수가 같은 가장 작은 수를 찾는 코드입니다.
bin(n).count("1")로 1의 개수를 비교하며 n+1씩 증가시키는 방식입니다.
is 대신 ==을 사용해야 하며, 반복문을 쓰면 더 효율적입니다.

'프로그래머스 > LV.2' 카테고리의 다른 글

[프로그래머스][LV.2] 최댓값과 최솟값 \| python3 (0)	2025.02.11
[프로그래머스][LV.2] 숫자의 표현 \| python3 (0)	2025.02.07
[프로그래머스][LV.2] 땅따먹기 \| python3 (0)	2025.02.06
[프로그래머스][LV.2] 3 x n 타일링 \| python3 (0)	2025.02.06
[프로그래머스][LV.2] 멀리 뛰기 \| python3 (0)	2025.02.05

꾸준히

꾸준히

태그

최근글

댓글

공지사항

아카이브