[ 알고리즘 ] LeetCode 13. Roman to Integer

이주 weekwith.me·2022년 8월 15일

목록 보기

65/73

블로그를 이전 중이라 완료되기 전까지는 벨로그에 작성할 계획입니다.
이후 모든 글은 https://weekwith.me 에 작성 예정이니 다른 글이 궁금하시다면 해당 링크를 통해 방문해주세요.

본 글은 [ LeetCode ] 13. Roman to Integer를 풀고 작성한 글입니다.

문제

요구사항

Roman numerals are represented by seven different symbols: I , V , X , L , C , D and M .

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

For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII , which is simply X + II . The number 27 is written as XXVII , which is XX + V + II .

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII . Instead, the number four is written as IV . Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX . There are six instances where subtraction is used:

I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer.

제약사항

1 <= s.length <= 15
s contains only the characters ('I', 'V', 'X', 'L', 'C', 'D', 'M') .
It is guaranteed that s is a valid roman numeral in the range [1, 3999] .

풀이

접근법

주어진 로마 숫자 문자열을 뒤집어서 계산하면 된다.

나의 풀이

접근법을 토대로 문제를 해결하면 아래와 같다.

def solution(s: str) -> str:
    answer: int = 0
    rome_to_integer: dict[str, int] = {
        "I": 1,
        "V": 5,
        "X": 10,
        "L": 50,
        "C": 100,
        "D": 500,
        "M": 1000
    }
    is_minus: bool = False
    previous_symbol: str = ""
    for symbol in s[::-1]:
        if symbol == "I":
            if previous_symbol == "V" or previous_symbol == "X":
                is_minus = True
        
        elif symbol == "X":
            if previous_symbol == "L" or previous_symbol == "C":
                is_minus = True
        
        elif symbol == "C":
            if previous_symbol == "D" or previous_symbol == "M":
                is_minus = True
            
        if is_minus:
            answer -= rome_to_integer[symbol]
        else:
            answer += rome_to_integer[symbol]
            
        is_minus = False
        previous_symbol = symbol
        
    
    return answer

다른 풀이

아래와 같이 더 간단하게 문제를 해결할 수 있다.

로마 숫자 문자열을 뒤집어서 하나씩 확인할 때 이전 로마 숫자보다 현재의 로마 숫자가 더 작은 경우 빼고 그렇지 않은 경우 더해주면 된다.

def solution(command: str) -> str:
    rome_to_integer: dict[str, int] = {
        "I": 1,
        "V": 5,
        "X": 10,
        "L": 50,
        "C": 100,
        "D": 500,
        "M": 1000
    }
    reversed_s: str = s[::-1]
    answer: int = rome_to_integer[reversed_s[0]]
    for idx in range(1, len(reversed_s)):
        current_value: int = rome_to_integer[reversed_s[idx]]
        previous_value: int = rome_to_integer[reversed_s[idx-1]]
        
        if current_value < previous_value:
            answer -= current_value
        else:
            answer += current_value
    
    return answer