Pythonで整数を3進数（基数3）の文字列に変換する方法

問題概要

ある整数 n が与えられたとき、その数を3進数（基数3）で表した文字列を求めることを考えます。

例えば、入力が 17 の場合、出力は「122」となります。これは 1×9 + 2×3 + 2×1 = 17 と計算できるためです。

なお、Pythonには2進数・8進数・16進数向けの bin()・oct()・hex() といった組み込み関数は存在しますが、3進数に対応する関数はないため、自前で変換処理を実装する必要があります。

解法のアプローチ

この問題は、次の手順で解くことができます。

• n が負の場合は符号「-」を記録しておき、n を絶対値に置き換える
• n が 3 未満の場合は、そのまま文字列として返す
• 空の文字列 s を用意する
• n が 0 になるまで以下を繰り返す
  • s の先頭に「n を 3 で割った余り（n mod 3）」を連結する
  • n を「n ÷ 3 の商」で更新する
• 最後に符号と s を連結して返す

これは「除算と剰余による進数変換」の定番手法で、仕組みさえ理解すれば任意の基数への変換に応用できます。各ループで得られる余りが下位の桁に対応し、n を 3 で割り続けることで上位の桁へと進んでいくイメージです。

処理の流れ（n = 17 の場合）

• 17 ÷ 3 = 5 余り 2 → s = "2"
• 5 ÷ 3 = 1 余り 2 → s = "22"
• 1 ÷ 3 = 0 余り 1 → s = "122"

このように桁を左から順に組み立てることで、正しい3進数表現が得られます。

実装例

以下がPythonでの実装コードです。

class Solution:
    def solve(self, n):
        sign = '-' if n < 0 else ''
        n = abs(n)
        if n < 3:
            return str(n)
        s = ''
        while n != 0:
            s = str(n % 3) + s
            n = n // 3
        return sign + s

ob = Solution()
print(ob.solve(17))

ポイントは、負の数にも対応できるよう最初に符号を取り出し、絶対値に対して変換を行う点です。これにより、例えば -10 を入力すると「-101」という結果が得られます。

入力

17

出力

122

まとめ

整数を3進数の文字列に変換するには、「3で割った余りを桁として蓄え、商で更新する」操作を0になるまで繰り返すのが基本です。時間計算量は O(log₃ n)、空間計算量も O(log₃ n) となり、非常に効率的なアルゴリズムです。同様の考え方は4進数や5進数など、他の基数への変換にもそのまま使えます。