[Algorithm] Integer to Roman

Question:

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

For example, 2 is written as II in Roman numeral, just two one's added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

I can be placed before V (5) and X (10) to make 4 and 9. 
X can be placed before L (50) and C (100) to make 40 and 90. 
C can be placed before D (500) and M (1000) to make 400 and 900.
Given an integer, convert it to a roman numeral.

Example 1:

Input: num = 3
Output: "III"
Explanation: 3 is represented as 3 ones.

 

Example 2:

Input: num = 58
Output: "LVIII"
Explanation: L = 50, V = 5, III = 3.

 

Example 3:

Input: num = 1994
Output: "MCMXCIV"
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

 

Constraints:

1 <= num <= 3999

 

주어진 문제는 input으로 받은 정수의 숫자를 로마 문자로 변경하는 문제입니다.

로마문자의 심볼을 알려주소 그 해당 숫자를 가르쳐 주고 있습니다.

 

Solution:

로마문자와 정수의 관계를 딕셔너리를 사용하여 저장합니다. 이때 문제에서 주어진 로마문자와 숫자의 관계중에 특이한 관계가 있는것까지 정의를 해줍니다. 예를들어 4의 경우 로마문자는 IV입니다. 이런식으로 4(IV),9(IX),40(XL),90(XC),400(CD),900(CM)의 경우까지 추가를 해 주었습니다. 그리고 정의는 역순으로 해주었습니다. 그래서 큰수부터 처리를 할수 있도록 해줍니다.

 

반복문을 이용하여 입력받은 정수와 로마문자의 숫자를 비교하여 입력받은 숫자와 비교를 하고 비교한것중 가장 큰수에 해당하는 로마문자를 결과값에 넣어주고 그만큼 입력받은 정수에서 로마문자 숫자만큼을 빼주는 과정을 계속 해줍니다.

그래서 입력받은 정수가 0이 될때까지 반복을 해줍니다.

public class Solution {
    public string IntToRoman(int num) {
        // Define Roman numerals 로마문자를 딕셔너리에 정의를 합니다.
        Dictionary<int, string> romans = new Dictionary<int, string>()
            {
                { 1000, "M" },
                { 900, "CM" },
                { 500, "D" },
                { 400, "CD" },
                { 100, "C" },
                { 90, "XC" },
                { 50, "L" },
                { 40, "XL" },
                { 10, "X" },
                { 9, "IX" },
                { 5, "V" },
                { 4, "IV" },
                { 1, "I" }
            };

        string res = string.Empty;
        
        while(num>0) // 입력받은 정수가 0이 될때까지 반복
        {
            // Compare input integer with roman numeral 
            foreach(var keynum in romans)
            {
                if (num >= keynum.Key) // 입력받은 남은 정수와 딕셔너리에 들어있는 값을 비교
                {
                    res += keynum.Value; // 해당 로마문자를 결과값에 더함
                    num -= keynum.Key; // 해당 로마문자 수만큼 입력 정수를 빼줌
                    break;
                }
            }
        }

        return res;
    }
}

We define dictionary to store the relationship between Roman symbols and values, also we define the relationship between a given Roman letter and a number which are exceptional. 
For example, for 4, the Roman symbol is IV. So we added 4(IV), 9(IX), 40(XL), 90(XC), 400(CD), 900(CM). And we did the definition in reverse order. So we can compare with large numbers first.

By comparing the number of Roman symbol with the value of Roman, the largest value of Roman symbol among the repeated sentences is added to the result, and the process of subtracting the value of Roman symbol from the input number is continued.

So repeat until the input number is zero.