Roman to Integer

/LeetCode

문제 해석

요약

로마자로 주어진 숫자를 정수로 표현하기.

전문

🇰🇷 번역

로마자로 숫자는 7가지 다른 심벌: I, V, X, L, C, D, M로 표현된다.

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

예를 들어, 2는 로마자로 II 표현되고, 이것은 단지 1(I)을 두개 붙여놓은 것이다. 12는 단순히 X과 II을 더한 XII로 표현한다. 27은 XXVII로 표현한다(역시 VV + V + II 처럼 더한 것이다).

로마자 수사는 보통 왼쪽에서 오른쪽으로 작은 숫자부터 큰 숫자로 쓰인다. 그러나, 4는 IIII가 아니고, IV처럼 쓰인다. 5의 앞쪽에 1이 있으므로 우리는 그것을 빼는 것으로 4를 만든다. 같은 원리로 9에도 적용이되어 IX로 쓰인다. 빼기가 사용되는 경우는 6가지이다.

  • I는 V와 X 앞에 놓아 4와 9를 표현한다.
  • X는 L과 C 앞에 놓아 40과 90을 표현한다.
  • C는 D와 M 앞에 놓아 400과 900을 표현한다.

로마자가 주어지면 정수로 변환하여라. input의 범위는 1부터 3999까지이다.

Input Output 해설
"III" 3
"IV" 4
"IX" 9
"LVIII" 58 L = 50, V= 5, III = 3.
"MCMXCIV" 1994 M = 1000, CM = 900, XC = 90 and IV = 4.
🇺🇸 원문

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.

Input Output Explanation
"III" 3
"IV" 4
"IX" 9
"LVIII" 58 L = 50, V= 5, III = 3.
"MCMXCIV" 1994 M = 1000, CM = 900, XC = 90 and IV = 4.

🤔 문제 해결 방법 구상

  1. 각 문자별로 대응되는 숫자는 바뀌지 않는다.

    • 객체를 사용하여 각 문자별 값을 할당한다.
  2. 왼쪽으로 갈수록 커진다는 규칙을 지킨다면 대응되는 값들을 그대로 모두 더하면 된다.

    • 주어진 문자열의 마지막부터 비교하는 것이 편리할 것 같다.
  3. 하지만, 예외 규칙을 살펴보면 왼쪽 숫자가 더 작다.

    • 그렇다면 왼쪽 값과 비교해서 작으면 빼면 될 것 같은데...
  4. 가장 왼쪽까지 비교가 끝나면 리턴.

코드 구현

/**
 * @param {string} s
 * @return {number}
 */

// 객체로 symbols 정의
const romanToInt = function(s) {
  const symbols = {
    "I": 1,
    "V": 5,
    "X": 10,
    "L": 50,
    "C": 100,
    "D": 500,
    "M": 1000
  }

  let result = symbols[s[s.length - 1]];

  for (let i = s.length - 2; i >= 0; i--) {
    if (symbols[s[i]] < symbols[s[i + 1]]) {
      result -= symbols[s[i]];
    } else {
      result += symbols[s[i]];
    }
  }

  return result;
};

결과 분석

Runtime: 160 ms
Memory Usage: 41.6 MB

반복문을 돌아야 하기 때문에, 시간 복잡도 O(n)이고, symbols와 result 처럼 처음 정의된 공간 외에 필요한 공간이 없으므로, 공간복잡도는 O(1)이다.

마무리

객체로 지정해 놓으면 값을 바로바로 찾을 수 있다. 정해진 값으로 대체해야 할 때, 객체를로 접근하면 편리하다.

Tags
Comments