[프로그래머스] 다음 큰 숫자 - Python

링크: https://school.programmers.co.kr/learn/courses/30/lessons/12911

프로그래머스

아이디어

• 조건 2와 조건 3의 관계를 찾는게 관건인 문제같다.
• 그냥 단순 for문을 돌아 1의 갯수를 카운트하여 다음 큰 수를 찾는 방법은 무리가 있을까?
• n이 1,000,000 이하여서 큰 영향은 없지 않을까?
• 일단 한 번 해보자

구현

def solution(n):
    #n을 2진수로 변환 후 1의 개수 카운트
    cnt1 = bin(n).count("1")
    tmp = 1
    #n을 1씩 키우며 2진수로 변환 후 1의 개수 카운트
    while True:
        n += 1
        cnt1_2 = bin(n).count("1")
        #1의 개수가 같아지면 while문을 빠져나옴
        if cnt1 == cnt1_2:
            break
    return n

 

앵 맞았다..

count()함수도 시간복잡도가 n이고 while문 안에 n이 들어가 n^2의 시간 복잡도를 가져 무조건 시간초과가 나올 것이라 생각했었는데 아니였다..

다음 큰 수가 나오는 경우가 생각보다 빠르게 찾아져서 그런가 아니면 문제가 시간복잡도를 n^2까지 허용해준건지 잘 모르겠다.

 

그런데

효율성 테스트를 보면 시간이 정말 안걸리는 것을 볼 수 있다.

이를 유추해보면 전자(다음 큰 수가 나오는 경우가 생각보다 빠르게 나오는거)가 맞는가보다. ㅇㅅㅇ

마무리

• 단순 반복문으로 풀는 방법은 누구라도 생각할 수 있다.
• 하지만 처음에 이렇게 쉽게 풀린다고? 시간초과가 나지 않을까? 생각했었는데 아니였다..
• 때로는 단순한게 최고일때가 있나보다..

또 2진수로 변환하는 방법인 bin()함수를 꼭 기억해두자..