[leet_code]Roman to Integer

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 one's 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.

Example 1:

Input: s = "III"
Output: 3
Explanation: III = 3.
Example 2:

Input: s = "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.
Example 3:

Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

Constraints:

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].

체크해야할 점

1. 문자열에서 비교가 불가능하다.
2. 문자열을 숫자로 매핑해줘야 한다.
3. 문자열에서 숫자랑 매핑한 후 문자열이 인덱스로 주어졌을 때 최적의 시간 복잡도를 제공하는 자료구조를 알아야 한다.
4. 제약조건을 정말 잘 읽어야 한다.

함정 포인트

1. 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.

이부분을 정말 꼼꼼히 읽어야 한다.

해결방법

먼저 나는 이러한 로마 숫자의 특성을 파악해보았다.

로마 숫자는 알파벳이다.

알파벳과 매핑하면서 시간 복잡도가 상수인 사전을 사용하자.

앞자리에 큰 수가 먼저오고, 뒤에 작은 숫자가 온다.

그러나 예외 사항이 있는데 작은 수가 앞에 먼저오고 뒤에 큰 수가 오면 큰 수에서 작은 수를 빼준다.
이러한 로직을 나는 구현해 보았다.
1. 앞의 숫자가 없거나 또는 앞의 숫자가 큰 경우 -> 정상적인 순서로 진행되는 경우
2. 앞의 숫자가 현재 숫자보다 적은 경우

이러한 로직에는 빈틈이 존재하는데 바로 CMIX 이런 경우가 존재한다.
위의 로직을 따라가면 C => 100 , M을 만났다 어라? 더 큰데? 뭐징 안대!!!!!!
위의 로직은 예외적 상황이지만 if문을 사용한다면, 일일히 뒷자리 까지 확인해야 하는 번거로움 때문에 고민을 하게 된다.

그래서 나는 이러한 경우를 방지하면서, 일괄적인 프로세스를 제공하기 위해
일단 더하고, 나중일은 나중에 생각하자 라는 탐욕적 아이디어를 넣어 보았다.

생각의 흐름은 이렇다. C ? 일단 더해! > M? 일단 더해! 어라 이전에 더한 것보다 크잖아? C*2 빼.

위의 생각을 정리한 것이 아래의 코드이다.

test case 작성

1. MCDIX case 1409
2. CMIX case 909
3. CMXIX case 919

class Solution:
    def romanToInt(self, s: str) -> int:
        answer = 0
        temp = 0
        
        dic = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
        for i in s:
            if dic[i] <= temp or temp == 0: # if the dic[i] is the first or just same case
                answer += dic[i]
                temp = dic[i]
                
            else:  
                answer -= 2 * temp
                answer += dic[i]
                temp = 0
        
        return answer