Integer to Roman

문제

---

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

Integer to Roman - LeetCode

 

나의 풀이

---

2가지 방법으로 풀이했다. 첫 번째 방법은 좀 naive한 풀이이고, 두 번째 방법은 변환의 규칙을 파악한 풀이이다.

SOL 1)

1. 문제에서 주어진 조건이 num의 범위가 [1,3999]이므로 이 범위 안에서만 변환을 생각하면 된다.
2. 예컨대, 256을 변환하려면 200+50+6으로 분해하여 각각을 변환하면 된다.
3. 여기서 알 수 있는 점이 천의 자리는 1000,2000,300의 세 가지 경우에 대한 변환이 필요하고, 백의 자리는 100,200,300,...,900의 10가지 경우, 십의 자리는 10,20,30,...,90의 10가지 경우, 일의 자리는 1,2,3,...,9의 10가지 경우데 대한 변환이 필요하다. 즉 다 합쳐도 33가지 경우 밖에 되지 않으므로 이들의 변환에 대해 dictionary에 저장해 매칭시켜 변환하면 된다.

SOL 2)

1. 다음과 같이 val과 sym을 선언한다. val = [1000,900,500,400,100,90,50,40,10,9,5,4,1], sym = ["M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"] val에서 각 수는 변환에서 체크해줘야 하는 체크포인트들이다.
2. index i를 0부터 증가시켜가면서 val의 값으로 나눠준 몫을 가지고 sym의 문자를 그 몫만큼 답에 이어붙여준다.(이 부분은 코드를 직접 보고 로직을 따라가는 것이 이해가 빠르다. 코드를 보면서 아래 3번의 예시를 적용시켜보기 바란다.)
3. 예컨대, num=80이라면 아래와 같은 과정을 거쳐서 십의 자리 8에 대한 변환이 끝난다. 이를 num>0인 동안 반복해주면 일의 자리까지의 변환이 완료된다.
4. 80 > 0
   80 // 1000 = 0 -> i = 0
   80 // 900 = 0 -> i = 1
   80 // 500 = 0 -> i = 2
   80 // 400 = 0 -> i = 3
   80 // 100 = 0 -> i = 4
   80 // 90 = 0 -> i = 5
   80 // 50 = 1 -> i = 6

 

코드

---

SOL 1)

    """
    version 1
    """
    def intToRoman(self, num: int) -> str:
        num_to_roman = {}
        # 1~9
        for i in range(1,4):
            num_to_roman[i] = 'I'*i
        num_to_roman[4] = 'IV'
        for i in range(5,9):
            num_to_roman[i] = 'V'+'I'*(i-5)
        num_to_roman[9] = 'IX'
        
        # 10,20,...,90
        for i in range(10,40,10):
            num_to_roman[i] = 'X'*(i//10)
        num_to_roman[40] = 'XL'
        for i in range(50,90,10):
            num_to_roman[i] = 'L'+'X'*((i-50)//10)
        num_to_roman[90] = 'XC'
        
        # 100,200,...,900
        for i in range(100,400,100):
            num_to_roman[i] = 'C'*(i//100)
        num_to_roman[400] = 'CD'
        for i in range(500,900,100):
            num_to_roman[i] = 'D'+'C'*((i-500)//100)
        num_to_roman[900] = 'CM'
        
        # 1000,2000,3000
        for i in range(1000,4000,1000):
            num_to_roman[i] = 'M'*(i//1000)
        
        s_num = str(num)
        unit = []
        for i in range(len(s_num)):
            unit.append(int(s_num[i])*10**(len(s_num)-i-1))
        ans = ""
        for u in unit:
            if u==0:
                continue
            ans += num_to_roman[u]
        return ans

 

SOL 2)

    """
    version 2
    """
    def intToRoman(self,num:int):
        val = [1000,900,500,400,100,90,50,40,10,9,5,4,1]
        sym = ["M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"]
        s = ""
        i = 0
        while num>0:
            for _ in range(num//val[i]):
                s += sym[i]
                num -= val[i]
            i += 1
        return s