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

문제

https://programmers.co.kr/learn/courses/30/lessons/12911?language=python3 

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

 

3가지 조건을 만족하여 주어진 숫자보다 큰 숫자를 찾아야 한다. 

 

내 풀이

1001110의 다음 숫자는 1010011이다.

 

1001110

1010011

 

다음과 같은 규칙을 발견했다. 

1. 뒤에서부터 1이 존재하다가 (혹은 연속되었다가) 0이 되는 지점에 1을 넣어준다.

2. 나머지 1들은 뒤에 몰아서 배치한다.

3. 모든 수가 1인 경우(111...)는 맨 앞에 1을 더하고 동일하게 나머지 1들을 뒤에 몰아서 (011...) 더한다.

 

로직

1. 주어진 숫자를 2진수로 변환한다.

2. 뒤에서부터 1이 존재하거나 (혹은 연속되거나) 0이 되는 index를 찾는다.

3 - 1. index가 존재한다면, index 앞까지의 배열을 잘라내어 1을 더한다.

3 - 2. index가 존재하지 않는다면(-1이라면), 빈 배열에 1을 더한다.

4. index뒤에 있는 string을 1을 오른쪽으로 몰아서 붙여준다. (count를 통해 1의 개수를 센 후에, 0들을 앞으로 1들을 뒤로 붙인다.)

*  앞에 1을 붙여주기 때문에, 1의 개수를 동일하게 하기 위해 count 한 1의 개수에서 하나를 빼준다.

 

 

코드

def makeTwo(n): #bin( ) 이라는 함수로 대체가능
    a = ""
    
    while (n >= 1):
        a = str(n % 2) + a
        n = (int)(n / 2)
        
    return a

def findIndex(n2): # 뒤에서부터 연속되는 1들을 끝내는 점을 찾음
    
    start = False
    end = False
    
    for i in range(1, len(n2) + 1):
        if not start:
            if n2[len(n2) - i] == '1':
                start = True
            else:
                continue
        
        if start and not end:
            if n2[len(n2) - i] == '0':
                end = True
            else:
                continue
        
        if start and end:
            return (len(n2) - i)

    return -1 # 1111 ...

def Merge(n2, index):

    Back = n2[(index + 1):]
    countOne = Back.count('1') # 시간 초과 해결
    countOne -= 1
    
    if index == -1:
        result = "1"
    else:
        result = n2[:index] + "1"
        
    result = result + ("0" * (len(Back) - countOne))
    result = result + ("1" * countOne)
    
    return result

def makeTen(n): # int ('2진수', 2) 로 대체 가능
    num = 0
    now = 1
    for i in range(1, len(n) + 1):
        if n[len(n) - i] == '1':
            num += now
        now *= 2
    return num

def solution(n):
    
    answer = 0
    
    n2 = makeTwo(n)
    index = findIndex(n2)
    result = Merge(n2, index)
    answer = makeTen(result)
    
    return answer

 

다른 사람의 풀이

주어진 숫자를 2진수로 바꾸어 1의 개수를 count 한 후에,

주어진 숫자에 1씩 더하면서, 2진수로 바꿨을 때 1의 개수가 같은 숫자를 return 하는 풀이를 보았다.

 

코드가 훨씬 간결했다. 완전 탐색이기에 시간이 많이 걸릴 것이라고 생각했는데 시간제한을 통과한다고 한다. 세 조건을 만족할만한 수가 가장 멀리 있다면 어느 정도인지를 고려하여 시간 복잡도를 다시 한번 생각해보아야겠다.