[LeetCode, 리트코드] Integer to Roman

 

1. Problem

 

로만 표기법은 7가지 다른 심볼로 나타내어 진다. I, V, X, L, C, D, M

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

예를들어 II 일 때는 1을 두 번 더한 것과 같다. 12이 일 때는 XII, X + II 를 더한 것을 의미한다. XXVVII는 XX + V + II를 더한 것을 의미한다.

 

로만 표기법은 왼쪽부터 오른쪽으로 큰 수에서 작은 수로 표기되어 진다. 그리고 여기서 4는 IIII로 나타내어 지지 않고 IV로 나타내어진다. 왜냐하면 4는 5바로 직전의 수 이므로 V에서 I를 빼면 된다는 의미이다. IV가 바로 그 뜻이다. 이런 규칙은 총 6가지의 경우가 있다.

 

IV = 4, IX = 9, XL = 40, XC = 90, CD = 400, CM = 900

 

주어진 정수에 대해 이것을 로만표기법으로 고치는 함수를 작성하라. 입력은 1에서부터 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"
Explanation: L = 50, V = 5, III = 3.

Example 5:

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

 

2. Solution

 

가장 큰 수부터 처리하자. 즉 M부터 I 순서대로 처리해야한다. 또한 쉽게 문제를 풀려면 까다로운 IV, CM 같은 6개의 케이스는 하나의 단위로 취급해서 처리하는 게 좋다.

3. What I solved

class Solution {
public:
    string intToRoman(int num) {
        
        int romanUnit[13] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        vector<string> romanSymbol = 
                        {"M", "CM", "D", "CD", "C", "XC", "L", 
                          "XL", "X", "IX", "V", "IV", "I"};
        
        string ret = "";
        int i = 0;
        while(num > 0){
            int unitNum =  num / romanUnit[i];
            for(int k=0; k<unitNum; ++k)
                ret += romanSymbol[i];
            num -= unitNum*romanUnit[i];
            ++i;
        }
        
        return ret;
    }
};