12. Integer to Roman

Difficulty: Medium

This question is a little bit tricky. Normally we iterate through target (num in this case) and find the corresponding symbol in the dictionary. However, this will get more complicated.

The easier way is to iterate through the dictionary (sorted in descending order) and find the largest value that is smaller than the target. Gradually subtract the value from the target until the target is 0.

class Solution:
    def intToRoman(self, num: int) -> str:
        int_to_roman = {
            1: "I",
            5: "V",
            4: "IV",
            10: "X",
            9: "IX",
            50: "L",
            40: "XL",
            100: "C",
            90: "XC",
            500: "D",
            400: "CD",
            1000: "M",
            900: "CM"
        }
        sorted_dict_arr = sorted(int_to_roman.items(), key=lambda x: x[0], reverse=True)
        symbols = []
        for value, symbol in sorted_dict_arr:
            if num == 0:
                break
            count, num = divmod(num, value)
            symbols.append(symbol * count)
        return "".join(symbols)