[Python] programmers, 다음 큰 숫자 Lv.2 (feat.bin, count, 이진수)

반짝반짝 알고리즘, 인프준

 

 

 

다음 큰 숫자

문제 링크

프로그래머스

 

문제 설명

자연수 '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 )입니다.

 

 

 

해결 과정

다음 큰 숫자는 2진수로 표현할 때 1의 개수가 같아야 하기 때문에 변수를 만들고 while문을 활용해서 구현해 보았습니다. 'n'을 2진수로 변환했을 때 1의 개수와 n+1 값을 2진수로 변환했을 때 1의 개수가 다르다면 n+1을 반복합니다. 그러다 1의 개수가 같은 값이 나오면 그 값을 10진수로 변환하여 반환하는 코드를 구현하였습니다. 

def solution(n):
    answer = ''                             # 결과 값
    countAwr = 0                            # 결과 값의 1의 개수
    countOne = format(n, 'b').count('1')    # n의 1의 개수
    
    while(countOne != countAwr):            # 1의 개수가 같으면 종료
        n += 1
        answer = format(n, 'b')             # format을 써서 2진수로 변환
        countAwr = answer.count('1')        # 1의 개수 확인
    
    return int(answer, 2)                   # 2진수를 10진수로 변환하여 반환

 

 

테스트 케이스와 효율성 테스트 모두 빠른 실행 시간을 보여주며 통과합니다.

 

 

bin, oct, hex 함수와 format 함수

내장함수인 bin() 함수를 써서 2진수로 변환할 수 있지만 다른 진수와 차별을 두기 위해 출력되는 '0b'를 제거해줘야 하기 때문에 format() 함수를 이용해서 변환하였습니다. 2진수는 Binary, 8진수는 Octal, 16진수는 Hexadecimal이며 각 앞 3개 스펠링을 써서 함수가 표현됩니다.

# 파이썬 내장함수 bin, oct, hex
B = bin(5) # 0b101
O = oct(5) # 0o5
H = hex(5) # 0x5

# format 함수

B = format(5, '#b') # 0b101
O = format(5, '#o') # 0o5
H = format(5, '#x') # 0x5

--> #을 제거하면 구분 문자를 삭제하고 출력해준다.
B = format(5, 'b') # 101

 

 

 

 

 

---

 

 

 

 

출처: 프로그래머스 코딩 테스트 연습,  https://school.programmers.co.kr/learn/challenges