[Algorithm]Programmers:次の大きな数字byPython

12332 ワード
programmers algorithm テキストリンク
[問題のショートカット]https://programmers.co.kr/learn/courses/30/lessons/12911

📌問題の説明


自然数nが与えられると、nの次の大きな数は以下のように定義される.
条件nの次の大きな数字はnより大きい自然数である.
条件nの次の大きな数字とnがバイナリに変換されたときの1つの数は同じである.
条件nの次の大きな数字は条件1,2を満たす最小の数字である.
たとえば、78(1001110)の次の大きな数字は83(1010011)です.
自然数nをパラメータとして指定すると、nの次の大きな数を返す解関数を完了します.
せいげんじょうけん
nは1000000以下の自然数である.

I/O例説明)
I/O例#1
問題の例を以下に示します.
I/O例#2
15(1111)の次の大きな数字は23(10111)です.

💡 問題を解く


解題したけどすごく気を使った(?)ハードコーディングです.
次の大きな数を見つけるために,バイナリ数に現れる可能性のある数を計算した.
3つの状況があると思います.

  • “1”の個数は2進数と同じである
    ex) 15 = 1111(2)
    答えは+1でなければなりません.11110(2)

  • バイナリ数の最後のビットは0ではありません.
    ex) 51 = 110011(2)
    『0』は最後に登場したBeat位と、その後初めて『1』で登場したBeat位(4番目の「0」と5番目の「1」の交換位置!)
    110011(2) → 110101(2)

  • バイナリ数の最後のビットは0です.
    ex 1) 26 = 11010(2)
    後から整数の検索を開始すると、[1](1)を境界として、[0](0)が最初に表示された位置に[1](1)を配置し、その後、その位置の後にすべての[1](1)を末尾に配置します.
    11010(2) → 11100(2)
    ex 2) 78 = 1001110(2)
    1001110(2) → 1010011(2)
    3番目の[0](0)は、[1](1)を境界とする最初の[0](0)が現れる位置であるため、[1](1)を配置し、次に存在する2つの[1](1)を末尾に配置します.
    ※12=1100(2)のように繰り返し文が終わっても欲しい「0」の位置が見つからない場合
    2進数長が1桁増える場合は、一番前の「1」と残りの「1」をともに後ろに置けばよい.
    1100(2) → 10001(2)
    • def solution(n):
    binary = bin(n)[2:]
    cnt = binary.count('1')
    if len(binary) == cnt:
        return int('0b' + '10'+'1'*(cnt-1),2)
    else:
        if binary[-1] == '1':
            for i in range(len(binary)-1, 0, -1):
                if binary[i] == '0':
                    return int('0b' + binary[:i] + '10' + binary[i+2:], 2)
        else:
            flag = False
            chk = 0
            for i in range(len(binary)-1, 0, -1):
                if binary[i] == '0':
                    flag = True
                if binary[i] == '1' and flag and chk == 0:
                    chk = 1
                    flag = False
                if binary[i] == '0' and chk == 1:
                    idx = i
                    count_1 = binary[idx+2:].count('1')
                    count_0 = len(binary[idx+2:]) - count_1
                    return int('0b' + binary[:idx] + '10' + '0' * count_0 + '1' * count_1, 2)

            else:
                count_1 = binary.count('1')
                count_0 = binary.count('0')
                return int('0b' + '10' + '0'* (count_0) + '1' * (count_1-1), 2)
    他人の解答
    自然数nの「1」の個数を変数(cnt)に格納し、n+1から1000000に増やして2進数に変換した場合、「1」の個数がcntに等しい場合、
    def solution(n):
    cnt = bin(n).count('1')
    for i in range(n+1, 1000001):
        if bin(i).count('1') == cnt:
            return i
    1000000は大きな数字だと思いますが、1つ増えるごとにタイムアウトするかもしれません...これは簡単な問題です.
    WebViewの初使用
    VimプラグインVundle