[알고리즘 - LeetCode] 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, two is written as II in Roman numeral, just two one's added together. Twelve is written as, XII, which is simply X + II. The number twenty seven 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. Input is guaranteed to be within the range from 1 to 3999.

1 ~ 3999까지의 범위로 이루어진 로만(roman) 숫자를 정수로 변환하라.
로마 숫자는 왼쪽에 가장 큰 수가 자리하고 오른쪽 방향으로 작은 수로 쓰여지는데, 단위가 있는 수(1, 5, 10, 50, 100 ...)보다 하나 작은 수들(4, 9, 40, 90 ...)은 큰 수 왼쪽에 작은 수를 표현한다.
다시 말해, 작은 수가 큰 수보다 오른쪽에 있는 경우에는 더해주고, 왼쪽에 있는 경우에는 빼주면 된다.

Example 1:

Input: "III"
Output: 3

Example 2:

Input: "IV"
Output: 4

Example 3:

Input: "IX"
Output: 9

Example 4:

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

Example 5:

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

---

풀이

로마를 헤집고 다녔던 그때에는 건물마다 붙어있는 로마 숫자를 읽는 게 매우 익숙했었는데 갑자기 알고리즘 문제로 보니 반갑기도 하면서 헷갈리기도 했다. 이런 식으로 다시 만나게 될 줄이야..

제출 코드

const romanToInt = function(s) {
    const numbers = {
      I: 1,
      V: 5,
      X: 10,
      L: 50,
      C: 100,
      D: 500,
      M: 1000
    };
    
    let result = 0;
    
    for (let i = 0; i < s.length; i++) {
        const num = numbers[s[i]];
        const nextNum = numbers[s[i + 1]];
        
        if (nextNum && num >= nextNum) {
            result += num;
        } else {
            if (!nextNum) return result + num;
        
            result -= num;
        }
    }
    return result;
};

작은 수가 큰 수에 오른쪽에 오더라도 하나의 자릿 수만 확인하면 된다.
예를 들어 1900을 표현하기 위해 MCM을 쓰는 것은 가능하지만, 1800을 위해 MCCM은 쓰는 것은 불가하다.
그러므로 항상 두 자릿 수만 비교하여 양 편에 수의 크기만을 비교해주면 되니 코드는 전혀 복잡하지 않다.
1. 객체로 로만 숫자 단위를 입력해두고
2. 문자열을 순회하며 현재 인덱스의 수와 다음 인덱스의 수의 크기를 비교해서
3. (일반적인 경우) 오른쪽에 더 작은 수가 있다면 더해주고
4. 오른쪽에 더 큰 수가 있다면 빼주도록 한다.

타 제출 코드와 실행 속도 비교

몇 번 코드를 실행해보고 느끼는 점인데 같은 코드로도 속도가 조금씩 빨라졌다.. 느려졌다 한다.
분명히 어제는 128ms에 위치했는데 오늘은 140ms에서 찍히는 것이.. 인터넷 속도도 관여되는 건가

개선 사항

while문 작성 코드

var romanToInt = function(s) {
    const map = {
        I: 1,
        V: 5,
        X: 10,
        L: 50,            
        C: 100,
        D: 500,
        M: 1000,
    }
    
    let sum = 0
    let i = s.length - 1
    let prev = 0
    
    while (i >= 0) {
        const cur = map[s[i]]
        
        sum += cur < prev ? -cur : cur
        
        i--
        prev = cur
    }
    
    return sum
};

실행 속도가 가장 빠른 코드는 아니고
1. while문으로 푼 것과
2. prev를 할당하면서 순회하는 것,
3. 삼항 연산자로 더하고 빼는 것이

간단하고 깔끔해서 가져와봤다. sum += cur < prev ? -cur : cur 이 부분이 마음에 든다..

변경 후 코드

/**
 * @param {string} s
 * @return {number}
 */
var romanToInt = function(s) {
    const numbers = {
      I: 1,
      V: 5,
      X: 10,
      L: 50,
      C: 100,
      D: 500,
      M: 1000
    };
    
    let result = 0;
    
    for (let i = 0; i < s.length; i++) {
        const num = numbers[s[i]];
        const nextNum = numbers[s[i + 1]];
        
        if (!nextNum) return result + num;
        
        result += num >= nextNum ? num : -num;
    }
    return result;
};

위의 코드 참고해 삼항 연산자 사용하여 if 조건문을 없애보았다. 가독성이 훨씬(?) 더 좋은지 까지는 모르겠지만 아무튼 훨씬 더 간결해지기는 했다.

연산과 if.. else문을 함께 사용할 때 참고할 것