はじめに
海外企業のテクニカルインタビューを受けた際に出題されたアルゴリズム問題です。多くの企業で採用されている一般的な問題なようですが、私自身は初めて見た問題でした。その時考えたプログラムを記録として残しておこうと思いました。解いて見て、スッキリしないコードだなぁというのが率直な感想です。こうしたらもっと良くなるなど、教えていただけると幸いです。
問題の概要
- 入力されたアラビア数字をローマ数字に変換して出力する
- アラビア数字に対応するローマ数字は対応表の通り
- 対象となるアラビア数字の範囲は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;
}
}