[Top Interview Questions] #13. Roman to Integer

정답)

class Solution:
    def romanToInt(self, s: str) -> int:
    	# 딕셔너리에 각 문자에 상응하는 정수를 저장.
        romanDic = {
            'I':1,
            'V':5,
            'X':10,
            'L':50,
            'C':100,
            'D':500,
            'M':1000
        }
        
        # 최종으로 리턴할 변수에 0번째 변환된 정수를 저장.
        res = romanDic[s[0]]
        
        for i in range(1, len(s)):
            # 선형할때마다 변환된 정수를 더해줌.
            res += romanDic[s[i]]
            
            # 하지만 특수상황이 발견되면 필요한만큼의 값을 다시 뺌.
            if s[i] in ['V', 'X', 'L', 'C', 'D', 'M']:
                if romanDic[s[i]] > romanDic[s[i-1]]:
                    res -= 2*romanDic[s[i-1]]
        
        return res

문제)

로마 숫자는 다음과 같이 표기됩니다:

 

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

로마 숫자는 보통 덧셈의 원리로 이루어집니다. 예를 들어, "II"는 1 + 1을 한 2. "CLI"는 100 + 50 + 1을 한 151이 됩니다.

 

하지만 뺄셈을 이용한 숫자 또한 존재합니다. 예를 들어, "IV"는 5 - 1을 한 4. "IX"는 10 - 1을 한 9가 되죠. 그래서 이런 원리로 뺄셈이 이루어지는 경우는 6가지가 있습니다:

 

• I가 V(5) 와 X(10) 전에 붙어 4와 9를 이루는 경우
• X가 L(50) 과 C(100) 전에 붙어 40과 90을 이루는 경우
• C가 D(500) 와 M(1000) 전에 붙어 400과 900을 이루는 경우

위와 같은 방식을 적용하여 주어진 로마 숫자를 정수로 변환하십시오. 

 

예시 1) "III" = 1 + 1 + 1 = 3

예시 2) "LVIII" = 50 + 5 + 3 = 58

예시 3) "MCMXCIV = 1000 + 900 + 90 + 4 = 1994

 

문제링크

풀이)

1) 딕셔너리 정의

저는 위와 같은 로마 차트를 봤을 때 딕셔너리가 떠올랐습니다. 저렇게 1:1로 예쁘게 정렬돼 있으면 한쪽은 key, 다른 쪽은 value로 저장하고 싶지 않나요?? 그러므로 주어진 그대로 딕셔너리에 저장해 주겠습니다.

 

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

2) 최종적으로 리턴할 변수

문제에서는 로마 숫자를 정수로 변환하여 리턴하라고 했습니다. 그리고 로마 숫자는 덧셈과 뺄셈을 원리로 하는 숫자입니다. 그래서 저는 최종적으로 리턴할 변수 res를 먼저 정의해 주고 그 변수에 0번째 로마 숫자의 정수값을 더해주었습니다. 

 

def romanToInt(self, s: str) -> int:
        romanDic = {
            'I':1,
            'V':5,
            'X':10,
            'L':50,
            'C':100,
            'D':500,
            'M':1000
        }
        
        res = romanDic[s[0]]

3) for문을 통해 덧셈

0번째 로마 숫자는 이미 더해졌으니 1번째 숫자들부터 선형검색하면서 로마 숫자를 발견합니다. 그 발견된 로마 숫자를 미리 저장해 둔 romanDic을 활용해 정수로 변환한 뒤 최종변수 res에 더해줍니다.

 

만약 s[i]가 'V'라면 romanDic['V']는 5이므로 res에 5를 더해줍니다. (딕셔너리에 'V'라는 key에 상응하는 value는 5입니다.)

 

def romanToInt(self, s: str) -> int:
        romanDic = {
            'I':1,
            'V':5,
            'X':10,
            'L':50,
            'C':100,
            'D':500,
            'M':1000
        }
        
        res = romanDic[s[0]]
        
        for i in range(1, len(s)):
            res += romanDic[s[i]]

4) 언제 뺄셈을 하나요?

그러나 "IV"나 "IX"와 같이 i번째 정수를 더하는 것이 아닌 뺄셈을 요구하는 상황이 오면 어떻게 할까요? 뺄셈을 요구하는 상황은 문제에서 알려줬다시피 6가지 경우입니다. 'V', 'X', 'L', 'C', 'D', 'M' 앞에 특수한 문자들 ('I', 'X', 'C') 이 앞에 오게 될 경우입니다. 그리고 그 특수한 문자들은 항상 상응되는 'V', 'X', 'L', 'C', 'D', 'M' 보다 작습니다.

 

'I'는 'V', 'X' 보다 작습니다.

'X'는 'L', 'C' 보다 작습니다.

'C'는 'D', 'M' 보다 작습니다.

 

만약 s[i]가 'V', 'X', 'L', 'C', 'D', 'M' 중 하나이고 그 앞전 로마 숫자가 s[i]보다 작을 때 우리는 뺄셈을 할 것입니다. 뺄셈을 할 때 주의할 점은 우리는 이미 앞전 로마 숫자를 더했습니다. 그러므로 1번 빼는 것이 아닌 2번을 빼줘야 합니다. 그리고 주어진 로마 숫자를 전부 선형검색했다면 최종변수 res를 리턴하면 됩니다.

 

def romanToInt(self, s: str) -> int:
        romanDic = {
            'I':1,
            'V':5,
            'X':10,
            'L':50,
            'C':100,
            'D':500,
            'M':1000
        }
        
        res = romanDic[s[0]]
        
        for i in range(1, len(s)):
            res += romanDic[s[i]]
            if s[i] in ['V', 'X', 'L', 'C', 'D', 'M']:
                if romanDic[s[i]] > romanDic[s[i-1]]:
                    res -= 2*romanDic[s[i-1]]
        
        return res

예시) 예시 3을 사용하여 풀어보겠습니다. 

s = "MCMXCIV"

 

res = 1000

 

(i=1)

res = 1000 + 100 = 1100

s[1]이 'C'이긴 하나 s[0]이 'M', 즉 s[1]이 s[0]보다 작음으로 뺄셈은 없습니다.

 

(i=2)

res = 1100 + 1000 = 2100

s[2]가 'M'이고 s[1]이 'C', s[2]가 s[1]보다 큼으로 뺄셈이 이루어집니다.

res = 2100 - 2(100) = 1900

 

...

 

(i=6)

res = 1991 + 5 = 1996

s[6]이 'V'이고 s[5]가 'I', s[6]이 s[5]보다 큼으로 뺄셈이 이루어집니다.

res = 1996 - 2(1) = 1994

 

output = 1994

 

 

풀이과정에 질문이나 잘못된 부분 있다면 알려주시면 감사하겠습니다 :)