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

프로그래머스 12911번 문제인 "다음 큰 숫자" Lv.2을 파이썬으로 풀어보도록 하겠습니다.

[프로그래머스] 다음 큰 숫자 Lv.2 - [파이썬/python]

 

 

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

 

---

💻 문제 설명

 

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

 

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

 

예를 들어서 78(1001110)의 다음 큰 숫자는 83(1010011)입니다.

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

 

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

프로그래머스

---

🚨 제한사항

 

• n은 1,000,000 이하의 자연수 입니다.

---

 

 

 

---

---

---

!!!정답 주의!!!

---

---

---

 

 

 

---

🌟 소스 코드

 

프로그래머스-다음-큰-숫자-파이썬-코드

 

def solution(n):

   

    # n을 2진수로 변환하고 1의 개수를 세어 n_count1에 저장

    n_count1 = bin(n).count('1')

   

    # n의 다음 숫자를 구하기 위해 next_n을 n+1로 초기화

    next_n = n + 1

   

    # 무한 루프

    while True:

       

        # next_n을 2진수로 변환하고 1의 개수를 세어서 n_count1과 같을시,

        # next_n이 우리가 찾는 숫자이므로 next_n을 반환(return)하고 함수를 종료

        if n_count1 == bin(next_n).count('1'):

            return next_n

       

        # next_n과 n_count1이 같지 않다면 next_n에 1을 더해 다음 숫자로 넘어갑니다.

        next_n += 1

 

 

---

⏱ 시간복잡도

 

위 코드의 시간 복잡도는 O(m)입니다.

 

 

- 2진수 변환 및 1의 개수 계산 bin(n).count('1')

n을 2진수로 변환하고 1의 개수를 세는 데 O(log n)의 시간이 소요됩니다. 이는 n을 2진수로 변환하는 데 필요한 시간 복잡도입니다.

 

- 루프 while True

n보다 큰 모든 숫자를 하나씩 확인하는 데 O(m)의 시간이 소요됩니다.

여기서 m은 n보다 크면서 n의 2진수 변환값의 1의 개수와 같은 첫 번째 숫자를 찾기 위해 필요한 단계 수입니다.

 

따라서, 전체 시간 복잡도는 루프에 소요되는 시간(O(m))이며, 이는 최악의 경우 n에 가까울 수 있습니다. 그러나 대부분의 경우, m은 n보다 훨씬 작습니다. 따라서 실제 실행 시간은 일반적으로 훨씬 빠를 수 있습니다.

 

이 방법은 n보다 큰 첫 번째 숫자를 찾을 때까지 모든 숫자를 검사하므로, 숫자가 많아도 효율적으로 동작합니다.

---

🏳‍🌈 테스트 결과

 

프로그래머스-다음-큰-숫자-상태

 

프로그래머스-다음-큰-숫자-테스트-결과