Help us understand the problem. What is going on with this article?

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

More than 1 year has passed since last update.

はじめに

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

問題の概要

  • 入力されたアラビア数字をローマ数字に変換して出力する
  • アラビア数字に対応するローマ数字は対応表の通り
  • 対象となるアラビア数字の範囲は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
5
1
2
3
4
5
出力.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;
    }
}
gght
某SIer企業で働く一方、フリーランスとしても活動しています。 これまでは、金融系、流通系のBtoBシステムの開発・運用などを担当。 将来、世界各国を旅しながら、オンライン上で仕事を完結させるビジネスモデルを確立すべく、現在奮闘中。
https://github.com/sn185171
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした