Integer to Roman(Hash Table,Math,String)

https://leetcode.com/problems/integer-to-roman/description/

Seven different symbols represent Roman numerals with the following values:

SymbolValue

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

Roman numerals are formed by appending the conversions of decimal place values from highest to lowest. Converting a decimal place value into a Roman numeral has the following rules:

• If the value does not start with 4 or 9, select the symbol of the maximal value that can be subtracted from the input, append that symbol to the result, subtract its value, and convert the remainder to a Roman numeral.
• If the value starts with 4 or 9 use the subtractive form representing one symbol subtracted from the following symbol, for example, 4 is 1 (I) less than 5 (V): IV and 9 is 1 (I) less than 10 (X): IX. Only the following subtractive forms are used: 4 (IV), 9 (IX), 40 (XL), 90 (XC), 400 (CD) and 900 (CM).
• Only powers of 10 (I, X, C, M) can be appended consecutively at most 3 times to represent multiples of 10. You cannot append 5 (V), 50 (L), or 500 (D) multiple times. If you need to append a symbol 4 times use the subtractive form.

Given an integer, convert it to a Roman numeral.

 

Example 1:

Input: num = 3749

Output: "MMMDCCXLIX"

Explanation:

3000 = MMM as 1000 (M) + 1000 (M) + 1000 (M)
 700 = DCC as 500 (D) + 100 (C) + 100 (C)
  40 = XL as 10 (X) less of 50 (L)
   9 = IX as 1 (I) less of 10 (X)
Note: 49 is not 1 (I) less of 50 (L) because the conversion is based on decimal places

Example 2:

Input: num = 58

Output: "LVIII"

Explanation:

50 = L
 8 = VIII

Example 3:

Input: num = 1994

Output: "MCMXCIV"

Explanation:

1000 = M
 900 = CM
  90 = XC
   4 = IV

 

Constraints:

• 1 <= num <= 3999

뭔 좀 난해한 문제는 아닌 거 같은데..

걍 Map, dictionary 간만에 써보라는 문제같다.

 

 

1. Python

쌉 노가다로 풀었는데 이게 맞나? 승률은 100프로 뜨긴했다;;

class Solution:
    def intToRoman(self, num: int) -> str:
        idx = 0
        ans = ""

        if num >= 1000: idx = 3
        elif num >= 100 : idx = 2
        elif num >= 10 : idx = 1
        else : idx = 0
        # num : 1000~3999
        if idx == 3:
            target = num//1000
            ans += "M"*target
            num -= 1000*target
            idx-=1
        # num : 999~100
        if idx == 2:
            target = num//100
            if target == 4:
                ans += "CD"
            elif target == 9:
                ans += "CM"
            else:
                if target<5:
                    ans += "C"*target
                else:
                    ans += "D"
                    ans += "C"*(target-5)
            num -= 100*target
            idx-=1
        # num : 99~10
        if idx == 1:
            target = num//10
            if target == 4:
                ans += "XL"
            elif target == 9:
                ans += "XC"
            else:
                if target<5:
                    ans += "X"*target
                else:
                    ans += "L"
                    ans += "X"*(target-5)
            num -= 10*target
            idx-=1
        # num : 9~1
        if idx == 0:
            target = num
            if target == 4:
                ans += "IV"
            elif target == 9:
                ans += "IX"
            else:
                if target<5:
                    ans += "I"*target
                else:
                    ans += "V"
                    ans += "I"*(target-5)
            num -= 10*target
            idx-=1

        return ans

뭔가 Dictionary를 써서 풀려면 이렇게 하면 될 거 같다..

40,90,400,900에 대한 놈들을 다 Mapping하는 것!

 

class Solution:
    def intToRoman(self, num: int) -> str:
        roman_map = [
            ("M", 1000), 
            ("CM", 900), 
            ("D", 500), 
            ("CD", 400),
            ("C", 100), 
            ("XC", 90), 
            ("L", 50), 
            ("XL", 40), 
            ("X", 10),
            ("IX", 9),
            ("V", 5),
            ("IV", 4), 
            ("I", 1)
        ]

        res = []
        for sym, val in roman_map:
            while num >= val:
                res.append(sym)
                num -= val
        
        return "".join(res)

이것도 아이디어긴 하네 ㅋㅋ..

 

이걸 응용해서 C++로 풀어봐야겠다.

 

 

2. C++

참고로 C++ MAP은 key-value search할 때 키 값 기준으로 lexicographical order로 정렬되어서 내 뜻대로 for문이 안 돌 수도 있다. 그래서 보통 vector + pair 조합을 많이 쓰는데, 그냥 pair 대신에 tuple을 써서 더 까불어봤다 ㅋ;

class Solution {
public:
    string intToRoman(int num) {

        vector<tuple<string,int>> m = {
            {"M",1000},
            {"CM",900},
            {"D",500},
            {"CD",400},
            {"C",100},
            {"XC",90},
            {"L",50},
            {"XL",40},
            {"X",10},
            {"IX",9},
            {"V",5},
            {"IV",4},
            {"I",1}
        };
        string ans = "";
        for(const auto pair : m){
            while(num >= get<1>(pair)){
                ans += get<0>(pair);
                num -= get<1>(pair);
            }
        }
        return ans;
    }
};