LeetCode 13(Roman to Integer, Python)

1. 문제 링크

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

2. 문제 설명

• 문제 자체는 심플, 로마 숫자를 정수로 반환하는 함수 (I, V, X ,L, .. 에 대응되는 정수값은 제공이 된다)
• 다만 숫자로 변환되는 규칙이 약간 생소 → 알고리즘 보다는 규칙을 찾는게 핵심
• 예시) II : 1+1=2, XII : 10+1+1=12, XXVII : 10+10+2+5=27
• 헷갈리는 규칙
  • 4는 IIII라 쓰지 않고, IV로 표현 - 5에서 1을 뺀 값으로 작성
  • I는 4,9를 만들기 위해 V,X 앞에 등장할 수 있고, X는 40,90을 만들기 위해 L,C앞에 등장 가능

3. 처음 풀이 

• 로마 문자를 key, 대응되는 정수를 value로 한 dictionary를 사전에 정의를 한 후,
• for문을 돌면서 로마 문자에 대응되는 숫자를 result_list에 append하되
• 첫 문자 이후부터는, value가 작은 로마문자가 앞에 등장했을 경우, 이전 value를 마이너스로 변환하는 과정을 추가
• 최종적으로 list의 합을 반환한다.
• 예시
  • MCMXCIV의 경우,
    • [1000, -100, 1000, -10, 100, -1, 5] 로 100, 10, 1이 음수로 변환이 되고, 해당 총합을 반환 → 1994

class Solution:
    def romanToInt(self, s: str) -> int:
        rom_dict = {
            'I' : 1,
            'V' : 5,
            'X' : 10, 
            'L' : 50,
            'C' : 100,
            'D' : 500, 
            'M' : 1000
        }

        result_list = []

        for i, char in enumerate(s): 
            if i == 0:
                result_list.append(rom_dict[char])
            else:
                if result_list[i-1] >= rom_dict[char]:
                    result_list.append(rom_dict[char])
                else: 
                    result_list[i-1] = -result_list[i-1] 
                    result_list.append(rom_dict[char])

        return sum(result_list)

• runtime 10%로 코드 개선이 필요해보이진 않았음. 

4. 다른 풀이 -1

• Submission에 있는 풀이 중에 괜찮았던 풀이
• 풀이가 거의 유사하나, 내 풀이에서는 i-1과 비교하면서, i==0일 때에 대한 조건을 따로 빼주었는데,
• iterator 도는 range를 1 빼고, i와 i+1을 비교하면서 result에 값을 더하거나 빼는 구조로 작성하고, 
• result에 가장 마지막 로마 문자에 대응하는 정수값을 더해서 반환. (쓰다보니 거의 비슷한것 같기도 함) 

class Solution:
    def romanToInt(self, s: str) -> int:
        rom_dict = {
            'I' : 1,
            'V' : 5,
            'X' : 10, 
            'L' : 50,
            'C' : 100,
            'D' : 500, 
            'M' : 1000
        }

        result = 0

        for i in range(len(s)-1):
            if rom_dict[s[i]] < rom_dict[s[i+1]]:
                result -= rom_dict[s[i]]
            else:
                result += rom_dict[s[i]]
            
        return result+rom_dict[s[-1]]

4. 다른풀이 -2

• 특이 or 참신했던 풀이 
• 예외가 되는 케이스들을 예외가 되지 않도록 replace를 한 후, 로마 문자에 대응되는 정수를 더하기만 한 구조.
• runtime은 큰 차이 없었음

class Solution:
    def romanToInt(self, s: str) -> int:
        translations = {
            "I": 1,
            "V": 5,
            "X": 10,
            "L": 50,
            "C": 100,
            "D": 500,
            "M": 1000
        }
        number = 0
        s = s.replace("IV", "IIII").replace("IX", "VIIII")
        s = s.replace("XL", "XXXX").replace("XC", "LXXXX")
        s = s.replace("CD", "CCCC").replace("CM", "DCCCC")
        for char in s:
            number += translations[char]
        return number

5. 배운 점

• 난이도 easy이기도 해서, 어려운 trick이 있진 않았다.
• 문제 속 규칙을 잘 뽑아내서 코드화 하기.