[프로그래머스/Level2] 다음 큰 숫자

문제 설명

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

 

---

나의 풀이

[Python(파이썬)]

def solution(n):
    one_cnt = format(n, 'b').count('1') # n의 이진수에서 1 개수

    for i in range(n+1, 1000001):
        if one_cnt == format(i,'b').count('1'):
            return i

 

---

학습한 내용

풀이 과정
1. 첫번째 풀이 -> 실패
2. 시간 초과 해결 풀이 -> 성공

 

1. 첫번째 풀이 -> 실패 

 

from itertools import permutations
def solution(n):
    tf, n = False, '0' + format(n, 'b')  # 10진수 -> 2진수
    temp = sorted(set(permutations(n,len(n)))) # 순열 -> 같은 숫자는 set을 통해 제거
    for i in temp:
        if tf == True:
            return int(''.join(i),2)
        if ''.join(i) == n:    # n을 찾았으면
            tf = True    # tf에 true -> 다음 값이 정답임을 알려줌

 

첫번째 풀이 알고리즘 

1) 10진수 n을 2진수로 변경해주기 
2) ex) '1111'일때 다음 큰 수는 10111 이므로 n에 '0' 추가해주기 ( n(2진수)와 n의 다음 큰 숫자(2진수)의 1의 갯수는 같다.)
3) 순열 구하기(set을 이용해 중복 제거)
4) temp에서 n과 같은 수를 찾으면 그 다음 숫자 10진수로 반환

 

풀면서 이번 문제는 생각보다 간단하다고 생각하면서 풀었는데 역시나,,, 시간 효율성이 관건인 문제였다. 

아무래도 순열을 사용해서 풀다보니 숫자가 커질수록 시간이 많이 걸리는 듯 했다. 

 

 

 

2. 시간 초과 해결 풀이 -> 성공

 

순열로는 아무래도 시간이 많이 걸리는 것 같아 다른 사람들 풀이에서 힌트를 얻었는데 바로 1의 개수에 관점을 두고 푸는 것이었다. 

 

def solution(n):
    one_cnt = format(n, 'b').count('1') # n의 이진수에서 1 개수

    for i in range(n+1, 1000001):
        if one_cnt == format(i,'b').count('1'):
            return i

 

시간 초과 해결 풀이 알고리즘 

1) 10진수 n을 2진수로 변경하여 1의 개수를 구하기
2) n+1 ~ 1000001까지 for문 돌리기 ( n은 1,000,000 이하의 자연수, 구하는 숫자는 n보다 커야하므로 n+1부터 시작 )
3) for문 변수 i의 2진수에서 1의 개수를 구한다음 n(2진수)의 1의 개수와 같은지 비교
4) 같다면 i 반환 다르다면 for문 계속 실행

 

 

확실히 시간이 엄청 줄었다. 다양하게 효율적으로 푸는 방법을 더 학습해야함을 느꼈다. 

 

 

---

문제 출처

코딩테스트 연습 - 다음 큰 숫자