다음 큰 숫자(이진수 변환)
문제 설명
자연수 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
15(1111)의 다음 큰 숫자는 23(10111)입니다.
문제풀이 IDEA
일단 주어진 숫자의 이진수 표현을 기준으로 동일 한 1의 갯수를 가지고
다음으로 큰 숫자를 찾는게 포인트였다.
그래서 규칙이 있는지 숫자들을 보았지만
10진수 표현에서는 규칙을 찾지 못했다..
그래서 이진수 변환 => 같은 1의 갯수를 기준으로 다음 큰수 찾기 => 다시 십진수변환
위의 과정을 python에서 제공하는 함수없이 구현해보았다.
나의 코드 (bin을 쓰지않고 직접 구현)
def solution(n):
cnt_pow = 0 #n을 2진수로 표현하기 위해 2의 몇 power인지 찾아내기 위한 변수(이진수 자리 관련)
n2 = n #n을 n2에 복사해서 차수를 찾기 위해 사용한다
t_digit = "" #이진수를 str의 형태로 만들어 준다
answer = 0
########이진수 변환 과정 ################
while n2 > 0: #예를 들어 5라면 5//2 == 2 -> 2 //2 == 1 --> 1//2 == 0 0
n2 = n2//2 #n2>1이 아니라 0으로 잡아준 이유는 5의 경우 101 이라는 이진수로 표현되기 때문에
cnt_pow += 1 #이진수의 자릿수 만큼 cnt_pow를 설정해주기 위해서다
for i in range(cnt_pow, 0, -1): #이진수의 특징을 보면 2^3 | 2^2 | 2^1 | 2^0 이런식으로 자리구성이
#구성이 되어 있으므로 역순으로 for문을 돌려 준다.
if n >= 2**(i-1): #대신 이진수의 자리수가 4라도 3~0 차수를 써야하므로 (i-1)을 해주고
t_digit += "1" #입력 받은 n이라는 값이 2**(i-1) 보다 크면 이진수에 1을 추가해주고
else: #아니면 0 을 가져온다
t_digit += "0"
n = n % 2**(i-1) #그리고 공통적으로 n값을 2**(i-1)로 나눈나머지를 n으로 저장해준다.
###############이진수의 (1의 갯수가 같으면서)다음으로 큰수 찾는 과정##############
t_digit = [int(i) for i in t_digit] #list comprehension으로 문자를 숫자로 바꾸어 다음으로 큰수를 찾기위한
#이진수 list를 만들어 준다.
t_digit2 = [int(i) for i in t_digit] #다른 방법으로도 할수 있겠지만 간단하게 기존의 1의 갯수가 몇개인지 기준점이 되는
#이진수도 list로 저장해 놓는다. (빠르기는 문자열에서 찾는게 더 빠르다)
#t_digit2 = t_digit.count("1") 이런식으로
while True:
t_digit[-1] += 1 #list의 끝자리 즉 이진수에 1을 더한다
for i in range(1, len(t_digit)+1): # for 문을 이용해서 list의 끝자리 부터 이진수 연산을 차례대로 수행해준다.
if i == len(t_digit): #만약 맨 앞자리까지 for문이 돌았다면 맨 앞자리가 2가 되었다는 의미이므로
t_digit[-i] = 0 #맨 앞자리를 0 으로 바꿔준다음
t_digit = [1]+t_digit #리스트의 앞부분에 1을 추가해줘 이진수의 자릿수를 늘려준다
if t_digit[-i] == 2: #이진수의 연산중에 2가 생성되면
t_digit[-i] = 0 #해당 자리를 0 으로 만든다음 상위 자리에 1을 더해주는 연산을 한다
t_digit[-i-1] += 1
if t_digit[-i] == 1: #만약 1을 더했는데 자리에 1이 와있다면 for문이 돌아갈 필요없이 종료된다.
break
if t_digit.count(1) == t_digit2.count(1): #그리고 while문은 계속 1을 더해가면서 연산하는 list와 기준점 list의 1이 같으면 탈출한다
break
###########10 진수 변환 과정 ################
for i in range(len(t_digit)):
answer += t_digit[i]*(2**(len(t_digit)-1-i)) #만들어진 이진수를 이용해 각 자리에 맞는 2의 power형태로 answer에 더해준다.
return answer
다른 코드 (bin 을 사용한 코드)
def nextBigNumber(n):
num1 = bin(n).count('1') #n을 bin함수를 이용해 바꿔준후 count를 이용해 1의 갯수를 찾아준다.
while True:
n = n + 1 #입력받은 n에서 1을 더해가며
if num1 == bin(n).count('1'): #1을 더한 값을 다시 이진수로 바꾸어 count로 1의 갯수를 찾아
break #기준이랑 일치하면 break해준
return n
출처 : 프로그래머스
