はじめに

海外企業のテクニカルインタビューを受けた際に出題されたアルゴリズム問題です。多くの企業で採用されている一般的な問題なようですが、私自身は初めて見た問題でした。その時考えたプログラムを記録として残しておこうと思いました。解いて見て、スッキリしないコードだなぁというのが率直な感想です。こうしたらもっと良くなるなど、教えていただけると幸いです。

問題の概要

入力されたアラビア数字をローマ数字に変換して出力する
アラビア数字に対応するローマ数字は対応表の通り
対象となるアラビア数字の範囲は0〜1000とする

対応表

対応表.md

Arabic  Roman
   1      I
   2      II
   3      III
   4      IV
   5      V
   6      VI
   7      VII
   8      VIII
   9      IX
  10      X
  40      XL
  50      L
  90      XC
 100      C
 500      D
 900      CD
1000      M

入出力例

入力.md

出力.md

I
II
III
IV
V

プログラム

アルゴリズム

考えたアルゴリズムは以下の通り

入力されたアラビア数字が対応表に記載された数字の場合、そのままローマ数字に変換。
対応表にない数字の場合(ex: 600)、対応表に記載された数字を組み合わせる必要がある。

　①対応表のアラビア数字を除数として、数字の大きい順{1000,900,500,...,1}に入力値を割り、商が1以上になるまで繰り返す。
　②①で生じた余りを再度、数字の大きい順{1000,900,500,...,1}に割り、商が1以上になるまで繰り返す。
　③①と②を繰り返し、余りが0になったら、除数として使用した全てのアラビア数字をローマ数字に変換して結合し、出力する。
　
ex)対象のアラビア数字が600の場合
　　①600/1000 -> 600/900 -> 600/500...の順に割っていく。
　　②余りが0になるのは500で割った後に100で割ったとき。
　　③余りが0となった時、除数として使用した数字は500と100であるため、DとCを結合し、DCを出力する。

実装

ソースはこちら

Main.java

public class Main {

    public static void main(String[] args) throws IOException {

        int arg = Integer.parseInt(args[0]);
        int roman[] = new int[arg];
        for (int i = 1; i < args.length; i++) {
            roman[i - 1] = Integer.parseInt(args[i]);
        }
        String returnRoman[] = new String[Integer.parseInt(args[0])];
        returnRoman = romanizer(roman);
        for (String show : returnRoman) {
            System.out.println(show);
        }
    }

    /**
     * アラビア数字をローマ数字へ変換する
     * @param ローマ数字へ変換する値
     * @return ローマ数字に変換された値
     */
    static String[] romanizer(int[] numbers) {

        String[] romReturn = new String[numbers.length];
        StringBuffer str;
        // 除数(divisor)
        int div = 0;
        // 余り(remainder)
        int rem = 0;
        int i = 0;
        Map<String, Integer> map = new HashMap<String, Integer>();

        // ローマ数字へ変換する値を一つずつ変換していく
        for (int arabic : numbers) {
            // 定数として宣言されている値はそのままローマ数字に変換する
            if (RomanEnum.isInRomanEnum(arabic)) {
                romReturn[i] = RomanEnum.getRoman(arabic);

            } else {
                // 定数に宣言されていない値は定数を使いながらローマ数字へ変換していく
                str = new StringBuffer();
                rem = arabic;
                while (rem != 0) {
                    // 値を割って除数と余りを算出
                    map = RomanEnum.getQuotAndRem(rem);
                    // 余りを取得
                    rem = map.get("remainder");
                    // 編集用の値に除数を格納
                    str.append(RomanEnum.getMapValue().get(map.get("divisor")));
                }
                romReturn[i] = str.toString();
            }
            i++;
        }
        return romReturn;
    }
}

RomanEnum.java

/**
 * アラビア数字とローマ数字を取り扱うEnum
 */
public enum RomanEnum {

    M(1000, "M")
    , CD(900, "CD")
    , D(500, "D")
    , C(100, "C")
    , XC(90, "XC")
    , L(50, "L")
    , XL(40, "XL")
    , X(10, "X")
    , IX(9, "IX")
    , VIII(8, "VIII")
    , VII(7, "VII")
    , VI(6, "VI")
    , V(5, "V")
    , IV(4, "IV")
    , III(3, "III")
    , II(2, "II")
    , I(1, "I");

    private int arabic;
    private String roman;
    private static Map<Integer, String> mapValue = new HashMap();

    // 除数
    private final static String DIVISOR = "divisor";
    // 余り
    private final static String REMAINDER = "remainder";

    private RomanEnum(int num, String roman) {
        this.arabic = num;
        this.roman = roman;
    }

    public int getArabic() {
        return arabic;
    }

    // フィールドの値をMap型で全て取得
    public static Map<Integer, String> getMapValue() {
        for (RomanEnum compareObj: values()) {
            mapValue.put(compareObj.arabic, compareObj.roman);
        }
        return mapValue;
    }

    // ローマ数字を取得
    public static String getRoman(int i) {
        return getMapValue().get(i);
    }

    // フィールドに値が存在する
    public static boolean isInRomanEnum(int i) {
        for (RomanEnum compareObj: values()) {
            if (compareObj.getArabic() == i) {
                return true;
            }
        }
        return false;
    }

    // 商が1以上になる時の除数と余りを返す
    public static Map<String, Integer> getQuotAndRem(int i) {
        Map<String, Integer> map = new HashMap<String, Integer>();
        for (RomanEnum compareObj: values()) {
            if (i / compareObj.getArabic() >= 1) {
                map.put(DIVISOR, compareObj.getArabic());
                map.put(REMAINDER, i - compareObj.getArabic());
                break;
            }
        }
        return map;
    }
}

【アルゴリズム問題】アラビア数字をローマ数字に変換する

はじめに

問題の概要

対応表

入出力例

プログラム

アルゴリズム

実装