12. Integer to Roman

將數字轉換為羅馬數字。

https://leetcode.com/problems/integer-to-roman/

羅馬數字的轉換規則可以參考這題

範例
Input: s = 1994
Output: "MCMXCIV"
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

這題其實也只是單純的數字轉換為文字，從千位數->百位數->十位數->個位數，逐步mapping對應的文字後再進行串接。

因為組合不多，真的用暴力解將30種幾組合全部寫下來也是可行，不過還是試著用少量的參數來解。

	public static String intToRoman(int num) {

		// 先將7種組合紀錄下來
		Map<Integer, String> map = new HashMap<>();
		map.put(1, "I");
		map.put(5, "V");
		map.put(10, "X");
		map.put(50, "L");
		map.put(100, "C");
		map.put(500, "D");
		map.put(1000, "M");

		// 答案的字串
		StringBuilder sb = new StringBuilder();
		// 6~8的組合，因為羅馬數字是先串1再串5，因此1的部份要另外記錄再跟5串接
		StringBuilder five = new StringBuilder();
		for (int i = 1000; i >= 1; i = i / 10) {
			five.setLength(0);
			// 取出最左邊一位數字
			int a = num / i;
			switch (a) {
			// 根據不同的數字和i，會從map中取出不同位數的羅馬數字
			case 3:
				sb.append(map.get(i));
			case 2:
				sb.append(map.get(i));
			case 1:
				sb.append(map.get(i));
				break;
			case 4:
				// 4，右側需要串此位數的羅馬數字5
				sb.append(map.get(i)).append(map.get(5 * i));
				break;
			case 5:
				sb.append(map.get(5 * i));
				break;
			case 8:
				five.append(map.get(i));
			case 7:
				five.append(map.get(i));
			case 6:
				five.append(map.get(i));
				// 6~8，需先加總完1的部份再串5
				sb.append(map.get(5 * i)).append(five);
				break;
			case 9:
				// 9，右側需要串上一位數(i*10)的羅馬數字
				sb.append(map.get(i)).append(map.get(i * 10));
				break;
			case 0:
			}
			// 扣除已計算的部份
			num = num - a * i;
		}
		return sb.toString();
	}

LeetCode上有使用拿Array來mapping的解答，複雜度會更低。