[leetcode][파이썬]Roman to Integer #003

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

 

 

 

---

 

 

 

오늘 풀어본 문제는 주어지는 로마어(Roman)를 숫자(정수형)로 변환하여 표현하는 문제이다.

 

 

풀이#1 - hashmap + loop

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

        result = 0
        length = len(s) - 1
        while length > -1:
            if hashmap[s[length]] >= result or hashmap[s[length]] == hashmap[s[length + 1]]:
                result += hashmap[s[length]]
            else:
                result -= hashmap[s[length]]
            length -= 1
        return result

해당 문제를 보자마자, 이 문제는 hashmap을 사용하면 좋겠다라고 생각이 들었다.

왜냐하면, hashmap을 이용하게 되면 불필요한 연산을 줄일 수 있을 뿐더러 값을 검색해 가져오기도 편하다고 생각했다.

 

아무튼, 로마어가 순서대로 숫자로 바꾸는 문제였으면 무척 쉬웠겠지만 고려해야할 조건이 있다.

   

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.

 

 

 

위 조건을 해석해보면,

V(5)과 X(10) 전에 나오는 I(1)은 각각 4와 9를 만들 수 있다.
L(50)과 C(100) 전에 나오는 X(10)는 각각 40과 90을 만들 수 있다.
D(500)과 M(1000) 전에 나오는 C(100)은 각각 400과 900을 만들 수 있다.

 

 

 

그러므로, 위 조건을 고려해야 했다.

처음에는 주어진 로마어를 0(start)부터 해당 길이만큼(len) 순차적으로 접근하여 풀어보려고 했지만, 당시 for문(loop)안에서 값을 빼줘야 하는 조건에서 다다음 인덱스로 넘어가는 부분이 매끄럽게 되지 않았다. 다풀고 보니 while문으로 고쳐서 접근했으면 left to right 접근 방법도 적절했다는 걸 알았다.

 

 

결국 본인은 다른 규칙을 찾았고, right to left 접근 방법이 있다는 걸 알았다.

End(len - 1)에서 Start(0)으로 순환하면서 

 

 

1. 현재 값(hashmap[s[length]])이 총합(result)과 같거나 클 경우 [조건1]

+ 현재값(hashmap[s[length]]) 이 그 전 값 (hashmap[s[length + 1]]) 과 같을 경우 [조건2]

==>  총합(result)에 현재 값 (hashmap[s[length]]) 을 더함

if hashmap[s[length]] >= result or hashmap[s[length]] == hashmap[s[length + 1]]:
result += hashmap[s[length]]

 

 

2. 나머지 경우, 총합(result)과 현재값(hashmap[s[length]])을 빼줌 

else:
    result -= hashmap[s[length]]

 

 

 

 

결과적으로, 로마어를 적절한 정수로 조건에 맞게 변환할 수 있었다.