[Leet Code] 12. Integer to Roman (Python, Swift)

[Leet Code] 12. Integer to Roman

오늘은 다른 사람들의 풀이를 보고 충격을 받아서,,, 내가 했던 실수를 되짚을 겸 최적화 하는 과정을 상세하게 적어보려고 한다.

먼저 이 문제를 처음 접했을 때, 기본으로 주어진 7가지의 표현을 딕셔너리에 넣어서 더하고 빼려고 했다. 그런데 좀만 더 생각해보니 시작하는 수가 4와 9일 경우에만 주어진 로마숫자에서 빼면 되기때문에 딕셔너리에 4, 9, 40, 90, 400, 900만 더 넣으면 빼는 것을 생각하지 않아도 된다.

그래서 일단 딕셔너리에 다 넣었다...

dic = {1: 'I', 5:'V', 10: 'X', 50: 'L', 100: 'C', 500: 'D', 1000: 'M', 4 :'IV',9:'IX', 40: 'XL', 90: 'XC', 400: "CD", 900: "CM"}

그리고 나는 자리수를 구별하기 위해 separate 함수를 만들어 각 자리 별 숫자를 리스트에 넣었다.

def separate(self, num: int, lst: list) -> list:
        if num // 10 == 0:
            lst.append(num%10)
            return lst
        lst.append(num%10)
        return self.separate(num//10, lst)

이를 이용한 초기 코드는 다음과 같다.

class Solution:
    def separate(self, num: int, lst: list) -> list:
        if num // 10 == 0:
            lst.append(num%10)
            return lst
        lst.append(num%10)
        return self.separate(num//10, lst)

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

        lst = self.separate(num, lst)
        for i in range(len(lst)):
            n = lst[i]*(10**i)
            if n in dic:
                answer = dic[n] + answer
            else:
                first = lst[i]
                sub = 10**i
                tmp = ""
                if first > 5:
                    first -= 5
                    tmp += dic[5*sub]
                tmp += dic[sub]*first
                answer = tmp + answer
        
        return answer
        

separate함수는 자리수를 원래 숫자의 순서와 반대로 저장한다. 이를 이용하여 자리수에 10**i만큼 곱해서 사용할 수 있었다.
하지만 이 코드는 가독성이 떨어지며 중복되는 부분이 있어 비효율적이다.

이를 개선하기위해 먼저 separate함수를 없앴다. 그리고 원래 숫자에서 dic에 있는 숫자 중 가장 큰 수부터 빼면서 불필요한 계산을 없앴다.

결과는 다음과 같다.

class Solution:
    def intToRoman(self, num: int) -> str:
        dic = {
            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'
        }
        
        roman_numeral = ""
        for value in dic.keys():
            while num >= value:
                roman_numeral += dic[value]
                num -= value

        return roman_numeral

코드가 훨씬 간결해졌고 가독성도 높아졌다!
하지만 이 코드는 숫자가 엄청나게 커진다면 전보다 비효율적일 수 있다.
왜냐하면 초기 코드는 숫자의 자리수에 비례하여 시간이 증가하지만 고친 코드는 숫자의 크기에 비례하여 시간이 증가하기 때문이다.

Chat GPT한테 두 코드를 비교해달라고 했다.

비교:
첫 번째 코드의 시간 복잡도: O(log10(N))
숫자의 자릿수(log10(N))에 비례하여 시간이 증가합니다.
두 번째 코드의 시간 복잡도: O(N)
숫자의 크기(N)에 비례하여 시간이 증가합니다.
결론:
첫 번째 코드(자리수 분리 및 각 자리수 처리)는 숫자의 자릿수(log10(N))에 비례하는 O(log10(N)) 시간 복잡도를 갖습니다.
두 번째 코드(딕셔너리를 사용하여 while 루프로 빼기)는 숫자의 크기에 비례하는 O(N) 시간 복잡도를 갖습니다.
이로 인해 첫 번째 코드가 매우 큰 숫자를 처리할 때 더 효율적입니다.

시간복잡도 측면에서만 봤을땐 이렇다고 한다!
그래도 복잡하게 생각했던 문제를 이렇게 간단하게 해결할 수 있구나 생각할 수 있어서 만족스러웠다.

Swift 코드는 다음과 같다.

class Solution {
    func intToRoman(_ num: Int) -> String {
        let dic: [(value: Int, symbol: 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")
        ]
        var result = ""
        var num = num
        for item in dic{
            while num >= item.value{
                result += item.symbol
                num -= item.value
            }
        }
        return result
    }
}