[프로그래머스 lv2] 다음 큰 숫자 (효율성 높은 풀이)

문제 설명

자연수 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 이하의 자연수 입니다.

입출력 예

입출력 예

입출력 예 설명

입출력 예#1
문제 예시와 같습니다.
입출력 예#2
15(1111)의 다음 큰 숫자는 23(10111)입니다.

---

나의 풀이

def solution(n):
    n = bin(n)[2:][::-1]+'0'
    zeros = n.find('1') # 0의 개수
    ones = n[zeros:].find('0') # 0 이후에 1의 개수
    answer = '1'*(ones-1) + '0'*zeros + '01' + n[ones+zeros+1:]
    return int(answer[::-1], 2)

이 문제를 푸는 방법은 여러 개겠지만 가장 먼저 생각할 수 있고 가장 단순한 방법이 반복문을 돌며 매번 2진수로 바꿔 1의 개수를 비교하는 방법이 있겠다. 나는 그 방법으로 풀어보지 않아서 잘 모르지만 아마 효율성 테스트에서 걸렸을 것이다. 이렇게 다 확인해 보는 것을 '완전 탐색' 이라고 한다.

내 생각에는 이 문제는 완전 탐색이 필요 없고, 패턴이 있을 것이라 생각해서 태블릿에서 숫자를 써놓고 한참을 들여다 보았다.

결국 패턴을 찾았다.

 그 전에 10진수의 숫자를 2진수로 바꾸는 방법은 다음과 같다.

10진수 -> 2진수

n = 10
bin_n = bin(n)
# 0x1010

bin_n = bin_n[2:]
# 1010

앞에 0x가 붙은 형태로 변형되며 타입은 str이 된다. 즉 이 2진수를 계산에 사용하려면 bin_n[2:] 와 같은 형태로 슬라이싱을 해서 사용하면 된다.

반대로 2진수의 숫자를 10진수로 바꾸는 방법은 다음과 같다.

2진수 -> 10진수

int('0x1010', 2)
# 10
int('1010', 2)
# 10

0x가 붙은 형태와 그렇지 않은 형태 모두 가능하다.

두 번째 인자로 해당 숫자가 몇 진수인지 입력한다. 만약 8진수라면 8로 적으면 된다.

풀이 패턴

78의 2진수 표현

'01' 패턴 찾기

0 1 패턴 찾기

오른쪽부터 왼쪽으로 탐색하며 0 1이 처음 나오는 부분을 찾는다.

찾은 0 1 부분을 맞바꾼다

발견한 0 1 부분을 서로 맞바꾼다.

맨 오른쪽에서 '0' 찾기

오른쪽 맨 끝에서 0 찾기

만약 맨 오른쪽 숫자가 1이라면 이 단계를 수행하지 않아도 이미 정답이다.

(즉, 숫자가 홀수라면 윗 단계에서 0 1을 1 0으로 맞바꾼 단계에서 이미 정답이 된다)

0이 오른쪽에 여러 개 있을 수 있다. 예를 들면 10010000 과 같은 경우 오른쪽 끝에 '0000' 이 있는 것이다.

찾은 0들을 왼쪽으로 밀기

찾은 '0'들을 앞서 맞바꾼 '0'을 만날 때까지 왼쪽으로 민다.

그럼 '1010011'이 답이 된다. (물론 다시 10진수로 바꿔야 한다)

 

코드로 풀어내기

숫자 표현

(여기서는 352를 가지고 변형하여 385가 나오는지 확인해본다. 352는 2진수로 바꾸면 101100000 이다.) 

352를 2진수로 표현

코드의 단순화를 위해 코드로 풀어낼 때는 2진수로 바꾼 수를 역순으로 바꿔서 계산한다.

위 2진수를 역순으로 표현

그리고 '1111'과 같이 '01' 패턴이 없는 경우를 대비해 맨 뒤에 '0'을 붙여준다. -> '11110 '

(역순으로 되돌리면 01111 이므로 1111 과 동일한 수이다.)

맨 끝에 0을 추가. (역순이기 때문에 동일한 수이다)

352(10진수) -> 101100000(2진수) -> 0101100000(앞에 0 추가) -> 0000011010 (역순)

n = bin(n)[2:][::-1]+'0'

 

0의 개수 세기

0의 개수 5개

zeros = n.find('1') # 0의 개수

역순으로 바꿨기 때문에 0의 개수는 왼쪽부터 세면 된다.

find 함수는 처음으로 해당 문자가 등장하는 인덱스를 반환하는데 인덱스는 0부터 시작하기 때문에 find('1') 로 찾으면 0의 개수를 알 수 있다.

zeros = 5 가 된다. (처음 등장하는 '1'의 index가 5이기 때문)

 

1의 개수 세기

1의 개수 2개

몇 개의 1이 밀려야 하는지 알아야 하기 때문에 1의 개수도 세어준다.

ones = n[zeros:].find('0') # 0 이후에 1의 개수

원리는 똑같다. 다만 위에서 zeros에 처음 발견한 1의 위치가 있기 때문에 해당 위치부터 마지막까지 중에서 확인하면 되는 것이다.

ones = 2 가 된다. (index 5 이후로 0이 2번째에 등장했기 때문)

패턴에 맞춰 계산하기

answer = '1'*(ones-1) + '0'*zeros + '01' + n[ones+zeros+1:]

ones에는 1의 개수, zeros에는 0의 개수가 저장되어 있다.

'1'들 중 하나는 '0'과 맞바꿔졌다. (여기서는 역순이기 때문에 '10' -> '01')

1들 중 하나는 맞바뀔 것이므로 1의 개수에서 1을 빼고 맨 앞으로 밀린다.

그렇기 때문에 ones에서 1을 뺀 수만큼 1이 가장 먼저 온다. (역순이기 때문에 다시 뒤집으면 맨 뒤로 간다)

-> '1'

그리고 '0'들을 그대로 밀어준다.

-> '1' + '00000' = '100000'

맞바꾼 결과인 '01'을 추가한다.

-> '100000' + '01' = '10000001'

이후 남은 숫자들을 뒤에 붙여준다.

-> '10000001' + '10' = '1000000110'

남은 애들의 인덱스는 zeros + ones + 1 부터 끝까지

 

뒤집어서 10진수로 바꾸고 return

'1000000110' 을 역순으로 다시 뒤집으면 '0110000001' 이 된다.

다시 역순으로 뒤집기

return int(answer[::-1], 2)

이를 역순으로 뒤집어 int 함수로 10진수로 바꿔주면 385가 된다.

 

정확성 테스트 결과

효율성 테스트 결과