[leetcode] Integer to Roman

임택·2021년 3월 11일
0

알고리즘

목록 보기
54/63

problem: 2

code

add 4xx 9xx where x is 0 or '', this problem becomes a lot easier.

class Solution {
    public String intToRoman(int num) {
        Map<Integer, String> map = new HashMap<>();
        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");
        int[] divider = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        
        StringBuilder sb = new StringBuilder();
        int share = 0;
        for (int j = 0; j < divider.length; j++) {
            int n = divider[j];
            share = num / n;
            num -= share * n;
                        
            for (int i = 0; i < share; i++)
                sb.append(map.get(n));
            
        }
        
        // map.keySet().forEach(System.out::println);
        
        return sb.toString();
        
    }
}

Time: O(1)
Space: O(1)

  • more
    public enum RomanNumeral {
        M("M", 1000),
        CM("CM", 900),
        D("D", 500),
        CD("CD", 400),
        C("C", 100),
        XC("XC", 90),
        L("L", 50),
        XL("XL", 40),
        X("X", 10),
        IX("IX", 9),
        V("V", 5),
        IV("IV", 4),
        I("I", 1);
        
        public String symbol;
        public int value;
        
        RomanNumeral(String symbol, int value) {
            this.symbol = symbol;
            this.value = value;
        }
    }
    public String intToRoman(int n) {
        StringBuilder result = new StringBuilder();
        for (RomanNumeral roman: RomanNumeral.values()) {
            if (n >= roman.value) { 
                int times = n / roman.value;
                for (int i = 0; i < times; ++i) {
                    result.append(roman.symbol);
                }
                n -= times * roman.value;
            }
        }
        return result.toString();
    }

2nd try: without adding 4xx, 9xx

profile
캬-!

0개의 댓글