LeetCode 12 – Integer to Roman

import java.util.TreeMap;

public class Solution {
  /*
Idea: First, convert a number, say 2034, into a list such as [4,30,0,2000].
Then, convert the individual components, and append together.

Rules: A subtractive pair must be of the following type
I followed by V or X
X followed by C or D
C followed by D or M

The rules are applied in order:
- First check if number is one of the numbers in the dictionary
- Then, check if it's possible to create a subtractive pair from it
- If not, finally do a normal conversion
- Take the least greatest than or equal element from the map, use it
, and convert the leftovers
   */

  TreeMap<Integer, String> tm;
  public String intToRoman(int num) {

    if(tm == null){
      tm = new TreeMap<Integer,String>();
      tm.put(1,"I");
      tm.put(5,"V");
      tm.put(10,"X");
      tm.put(50,"L");
      tm.put(100,"C");
      tm.put(500,"D");
      tm.put(1000,"M");            
    }

    String result = "";

    for(int i : convert(num)){
      result = intToRoman(i,tm) + result;
    }

    return result;
  }

  public String intToRoman(int num, TreeMap<Integer,String> tm){
    if(num == 0) return "";
    else if(tm.containsKey(num)) return tm.get(num);
    else{
      // Try subtractive order first
      String s1 = tm.get(num+1);
      String s2 = tm.get(num+10);
      String s3 = tm.get(num+100);

      if(s1 != null && (s1.equals("V") || s1.equals("X"))){
        return "I" + s1;
      }
      else if(s2 != null && (s2.equals("L") || s2.equals("C"))){
        return "X" + s2;
      }
      else if(s3 != null && (s3.equals("D") || s3.equals("M"))){
        return "C" + s3;   
      }
      else{ // no valid subtractive order, make the number normally
        int lt = tm.floorKey(num);
        return tm.get(lt) + intToRoman(num-lt,tm);
      }
    }
  }

  private ArrayList<Integer> convert(int n){
    ArrayList<Integer> res = new ArrayList<Integer>();
    int l = (int)(Math.log(n)/Math.log(10)) + 2;
    for(int i = 10; i <= Math.pow(10,l); i *= 10){
      res.add(n % i);
      n -= n % i;
    }
    return res;
  }

}