## Convert an integer to a roman numeral (Integer to Roman)

Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 to 3999.

Thoughts:
Not a hard problem. Only tricky point is that 4 is “IV” not “IIII”, 9 is “IX” not “VIIII” or “VIV”. First, we might think the bases are { 1000, 500, 100, 50, 10, 5, 1}, but if we use bases { 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 }, this problem would become really easy.

Code (C++):

```class Solution {
public:
string intToRoman(int num) {
setup();
string s;
for(map<int, string>::reverse_iterator it = romanMap.rbegin();
it != romanMap.rend(); ++it) {
while(num >= it -> first) {
s += it -> second;
num -= it -> first;
}
}
return s;
}

private:
map<int, string> romanMap;

void setup() {
romanMap[1000] = "M";
romanMap[900] = "CM";
romanMap[500] = "D";
romanMap[400] = "CD";
romanMap[100] = "C";
romanMap[90] = "XC";
romanMap[50] = "L";
romanMap[40] = "XL";
romanMap[10] = "X";
romanMap[9] = "IX";
romanMap[5] = "V";
romanMap[4] = "IV";
romanMap[1] = "I";
}
};

Code (Java):
public class Solution {
private static int[] bases = { 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9,
5, 4, 1 };
private static HashMap<Integer, String> map = new HashMap<Integer, String>();

private static void setup() {
map.put(1, "I");
map.put(4, "IV");
map.put(5, "V");
map.put(9, "IX");
map.put(10, "X");
map.put(40, "XL");
map.put(50, "L");
map.put(90, "XC");
map.put(100, "C");
map.put(400, "CD");
map.put(500, "D");
map.put(900, "CM");
map.put(1000, "M");
}

public String intToRoman(int num) {
setup();
String result = new String();
for (int i : bases) {
while (num >= i) {
result += map.get(i);
num -= i;
}
}
return result;
}
}

__ATA.cmd.push(function() {
__ATA.initVideoSlot('atatags-370373-5b2deafd4e659', {
sectionId: '370373',
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-26942-5b2deafd4e6a7',  {
collapseEmpty: 'before',
sectionId: '26942',
width: 300,
height: 250
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-114160-5b2deafd4e6aa',  {
collapseEmpty: 'before',
sectionId: '114160',
width: 300,
height: 250
});
});