[알고리즘] #Roman to Integer

문제 출처: https://leetcode.com/problems/roman-to-integer/

Roman to Integer - LeetCode

 

 

문제 해석

로마 숫자 표기법으로 만들어진 문자열 s가 주어졌을 때, 이를 정수로 변환하는 메서드를 만들어야 한다.

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

"IV": 4,
"IX": 9,
"XL": 40,
"XC": 90,
"CD": 400,
"CM": 900

 

 

 

문제 풀이

 

최초)

로마자를 두자리/한자리로 나눠 key-value 구조로 정의했다. 그리고 먼저 두글자로 된 로마자를 정수로 치환했다.

두자리로 된 로마자에 해당하는 문자(key)가 있을 때 sum에 해당 value 값을 더하고, 문자는 지워버린다.

그 다음 한자리로 된 로마자에 해당하는 정수 값을 sum에 더해준다.

 

이렇게 하면 테스트는 통과했지만 런타임 시간이 평균보다 오래 소요되는 것을 볼 수 있다. 아무래도 반복문 때문인 것 같은데 런타임 시간을 줄일 수 있는 방법을 고민해봐야겠다.

const single = {
    "I": 1,
    "V": 5,
    "X": 10,
    "L": 50,
    "C": 100,
    "D": 500,
    "M": 1000
}

const doubles = {
    "IV": 4,
    "IX": 9,
    "XL": 40,
    "XC": 90,
    "CD": 400,
    "CM": 900
}

var romanToInt = function(s) {
    let sum = 0

    // doubles 순회
    for (const key in doubles) {
        if (s.includes(key)) {
            sum += doubles[key]
            s = s.replaceAll(key, "")
        }
    }

    // single 순회
    Array.from(s).forEach(roman => {
        if (single[roman]) {
            sum += single[roman]
        }
    })

    return sum
};