[zerojudge]a013. 羅馬數字

a013. 羅馬數字

這題是現在遇到最有難度的問題，不花點時間想想還真解不出來。 羅馬數字的規則：

羅馬數字	數目
I	1
V	5
X	10
L	50
C	100
D	500
M	1,000

加法規則

依據上表由大到小加起來表示數目
e.g.

• 1 = I
• 3 = III
• 5 = V
• 7 = VII
• 110 = CX

減法規則

依據上表由小到大組成，表示大數目減小數目，遇到4、9時適用
e.g.

• 4 = 5 - 1 = IV
• 9 = 10 - 1 = IX
• 40 = 50 - 10 = XL
• 99 = 90 + 9 = (100 - 10) + (10 - 1) = XC + IX = XCIX
• 110 = CX

羅馬字和整數的表格轉換成一個字串roman和整數陣列num，
roman = "IVXLCDM"
num = {1, 5, 10, 50, 100, 500, 1000}
每個字元的位置對應到num的值，num[roman.indexOf(要查詢的字元)]。


解題分兩個部份：

一、羅馬轉整數

讀入字串後依據左到右的順序，判斷是大到小還是小到大進而決定適用哪種規則。判斷的方法是字元兩個兩個比對，0號和1號比，1號和2號比…以此類推。 為了避免最後一個字元沒有可以比對的對象，在字串後面加上一個"I"。 如果是小到大即加法規則，把加進結果中。大到小就相減再加進結果。

二、整數轉羅馬

把整數的每個位數分開，像是把1998拆成{1, 9, 9, 8}接著存入陣列中。 這個簡單，只要一直除10就好。 因為羅馬數字是從大的開始書寫，所以逆向處理陣列(e.g. 1->9->9->8變成8->9->9->1)，
轉換結果會有幾種：

• 9: 10-1
• 6~8: 5+(1~3)
• 5: 5
• 4: 5-1
• 0~3: 0~3

陣列的索引(index，中文是叫做索引嗎我忘了)也代表了位數（個十百千），索引的值*2可以對應到num，個位數索引是0，對應到num的I(1)， 0+1=1對應到num的V(5)，0+2對應到num的X(10)， 十位數索引是1，乘二=2，對應到num的X(10)，2+1=3對應到num的L(50)…以此類推。

程式碼如下：

/* a013:羅馬數字
*
* 2020/2/27
*
*/

import java.util.Scanner;

public class Pa013{

    static String roman = "IVXLCDM";
    static int[] num = {1, 5, 10, 50, 100, 500, 1000};

    public static void main(String [] args){
        Scanner scanner = new Scanner(System.in);

        while(scanner.hasNext()){
            String word = scanner.next();
            if(word.equals("#")) return;
            int a = romanToInt(word);
            int b = romanToInt(scanner.next());
            System.out.println(intToRoman(Math.abs(a - b)));
        } 
    }

    public static int romanToInt(String s){
        s += "I";
        int result = 0;

        for(int i = 1; i < s.length(); i++){
            int current = num[roman.indexOf(s.charAt(i - 1))];
            int next = num[roman.indexOf(s.charAt(i))];

            if(current >= next){
                result += current;
            }else{
                i++;
                result += next - current;
            }
        } 
        return result;
    }

    public static String intToRoman(int val){
        if(val == 0) return "ZERO";

        int[] nums = new int[(int)Math.log10(val) + 1];
        String result = "";

        for(int i = 0; i < nums.length; i++){
            nums[i] = val % 10;
            val /= 10;
        }

        for(int i = nums.length - 1; i >= 0; i--){
            if(nums[i] == 9){
                result += roman.charAt(i * 2);
                result += roman.charAt(i * 2 + 2);
            }else if(nums[i] >= 5){
                result += roman.charAt(i * 2 + 1);
                for(int j = 0; j < nums[i] - 5; j++){
                    result += roman.charAt(i * 2);
                }
            }else if(nums[i] == 4){
                result += roman.charAt(i * 2);
                result += roman.charAt(i * 2 + 1);
            }else{
                for(int j = 0; j < nums[i]; j++){
                    result += roman.charAt(i * 2);
                }
            }
        }

        return result;
    }
}