[LeetCode] Roman to Integer

https://leetcode.com/problems/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, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II. The number 27 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.

Example 1:
Input: s = "III"
Output: 3
Explanation: III = 3.

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

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

Constraints:
- 1 <= s.length <= 15
- s contains only the characters ('I', 'V', 'X', 'L', 'C', 'D', 'M').
- It is guaranteed that s is a valid roman numeral in the range [1, 3999].

고민

해당 문제는 로마 숫자를 정수로 변환하는 문제이다. 
단순하게 생각하면 로마 숫자와 정수를 맵핑해서 처리하면되지 않나? 라고 생각하지만 그리 쉽게 생각하기엔 조건이 많다.

특정 숫자 4, 9는 앞의 숫자가 더 작을 경우 뺄셈 규칙이 필요하다.

해결

class Solution {
    fun romanToInt(s: String): Int {
        val map = mapOf(
            'I' to 1,
            'V' to 5,
            'X' to 10,
            'L' to 50,
            'C' to 100,
            'D' to 500,
            'M' to 1000
        )

        var total = 0
        var prevValue = 0

        for (char in s.reversed()) {
            val current = map[char]!!
            if (current < prevValue) {
                total -= current
            } else {
                total += current
            }
            prevValue = current
        }
        return total
    }
}

일단 고민했던것처럼 map으로 기준을 만들고 거꾸로 계산했다.
왜냐하면 이전 값이 작다면 뺄셈이 필요하기 때문에 이렇게 처리했다.

결과

역시나 Runtime 에서 소요된 시간이 좋지않다.

후기

class Solution {
    fun translate(ch: Char): Int {
        return when(ch){
            'I'  ->           1
            'V'  ->     5
            'X'  ->      10
            'L' ->             50
            'C' ->             100
            'D' ->             500
            'M' ->             1000
            else -> 0
        }
    }

    fun romanToInt(s: String): Int {
        var answer = 0
        var prev = 0
        for(i in s){
            val current = translate(i)
            answer += if(current > prev){
                current - prev*2
            }else{
                current
            }
            prev = current
        }
        return answer
    }
}

3ms 소요된 코드이다. 나는 map으로 만든것을 이 사람은 when 문으로 처리했다. 이게 메모리상에는 더 나은 방법인것같다.
본 계산처리는 또 다른 함수로 정의를 했는데, 나랑 비슷하면서도 조금 다르다.

이 사람은 거꾸로가 아니라 정방향으로 루프를 도는데, `current - prev * 2` 부분이 특이하다.
순서대로 한번 차근차근 보자면, current 가 prev 보다 크면 prev 를 곱하여 current 에서 뺀 값을 answer 에 더하는 방식이다.
Example 에 나온 'MCMXCIV'를 확인해보자.

첫번째 요소인 M 의 값은 '1000' 이고 prev 는 0이기 때문에 answer 는 1000.
두번째 요소인 C 의 값은 '100'이고 prev 는 1000 이고 current 는 100 임으로 조건에 부합하지 않으니 answer는 1100.
세번째 요소인 M 의 값은 '1000'이고 prev 는 100, current 는 1000 임으로 조건에 부합하게 된다.
1000 - (100 * 2) = 800 임으로 answer 는 1900 이게 된다.

내가 지금 구하고자 하는 값보다 작은 값이 오게 되면 숫자를 뺀 효과를 주기 위해 이러한 방식을 사용한다.
나도 뺄셈이 필요하다고 판단하여 처리하긴 했지만, 내 방법은 왜 오래걸린걸까?

일단 한번 map 을 없애고 when 문으로 바꿔서 다시 runtime 을 확인해보자.

class Solution {
    fun romanToInt(s: String): Int {
        var total = 0
        var prevValue = 0

        for (char in s.reversed()) {
            val current = findValueByRoman(char)
            if (current < prevValue) {
                total -= current
            } else {
                total += current
            }
            prevValue = current
        }
        return total
    }

    private fun findValueByRoman(char:Char):Int = when (char) {
        'I' -> 1
        'V' -> 5
        'X' -> 10
        'L' -> 50
        'C' -> 100
        'D' -> 500
        'M' -> 1000
        else -> 0
    }
}

map 을 삭제하고 when 으로 바꾸니 9ms 나 줄어들었다.
내 방법도 틀린 방법은 아니었지만 Map 때문이었구나........ 하하...