Leetcode - Integer to Roman

Ji Kim·2020년 9월 18일
0

Algorithm

목록 보기
20/34

Leetcode : Integer to Roman

Description

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

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

Example 1

Input

3

Output

III

Example 2

Input

4

Output

IV

Example 3

Input

9

Output

IX

Example 4

Input

58

Output

LVIII
// L = 50, V = 5, III = 3

Example 5

Input

1994

Output

MCMXCIV
// M = 1000, CM = 900, XC = 90 and IV = 4

Approach

Create seperate arrays - symbol & value - and add the corresponding symbol to the string - result for quotient times.

Solutions

Solution I (C++)

class Solution {
public:
    string intToRoman(int num) {
        string symbol[13] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        int value[13] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};

        int i = 0; 
        int quotient = 1; 
        string result = "";
        
        while (num != 0)
        {
            quotient = num / value[i];
            
            for (int k = 0; k < quotient; k++)
            {
                result = result + symbol[i];
            }
            
            num = num - (quotient * value[i]);
            i = i + 1;
        }
        return result;
    }
};

Result

Runtime: 12 ms
Memory Usage: 6 MB
Runtime Beats 71.47% of C++ Submission

Solution II (JavaScript)

let intToRoman = function(num) {
    let roman = ['M', 'CM', 'D', 'CD', 'C', 'XC', 'L', 
                 'XL', 'X', 'IX', 'V', 'IV', 'I'];
    let numbers = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1];
    let result = '';
    
    numbers.forEach(function(value, index) {
        if(num > 0) {
            if(Math.floor(num / value) > 0) {
                let times = Math.floor(num / value); 
                num = num - (times * value);
                
                while(times > 0) {
                    result = result + roman[index]; 
                    times--; 
                }
            }
        }
    });
    return result; 
};

Result

Runtime: 148 ms
Memory Usage: 40.5 MB
Runtime Beats 91.70% of JavaScript Submission

profile
if this then that

0개의 댓글