Leetcode - 13. Roman to Integer - Easy

오늘의 문제는 로마 숫자를 아라비아 숫자로 바꾸는 로직을 만드는 것이다.

 

우선 로마자의 규칙 부터 알아야 한다.

 

위 그림에서 나왔듯이 M은 1000 이고 ... I 는 1 이다.

그러면 순서대로 MDCLXVI 이렇게 쓰면 이건 아라비아 숫자로 무엇일까?

일단 M은 1000이고 D는 500 이다. 그러면 여기 끼지는 두 숫자를 더해서 1500이 된다.

그런데 다음은 C이고 100을 의미한다. 그러면 1500에서 100을 더해서 1600이 된다.

이렇게 숫자들을 더하면 된다. 

그러면 1600 + 50 (L) + 10 (X) + 5 (V) + 1 (I) = 1666.

이렇게 MDCLXVI는 1666을 의미한다.

 

1. 여기서 알아낸 첫번째 규칙은 각각의 로마자에 대입되는 숫자들을 더하는데 기본 규칙이라는 것을 알 수 있다.

 

그러면 MCM는 어떻게 될까?

첫번째 M은 1000이다. 두번째 C는 100이다. 그리고 세번째 다시 M 즉 1000 이다.

단순히 이 세계를 더하는데 답일까? (1000 + 100 + 1000 = 2100 ???)

아니다. 여기서 한가지 더 알아야 한다.

900을 표시하기 위해서 C를 아홉 번 쓴다던가 D를 한번 쓰고 C를 4번 써서 900을 표시하지 않는다.

1000 쪽에 100을 쓰면 이건 빼라는 얘기다.

즉 CM 이렇게 쓰면 1000 (M) - 100 (C) = 900이 된다.

 

2. 여기서 두번째 규칙이 나온다. 현재 숫자보다 다음 숫자가 더 클 경우는 다음 숫자에서 현재 숫자를 뺀다이다.

 

MCMXCIV는 어떨까?

1000 + 900 (M-C) + 90 (C - X) + 4 (V-I) = 1994 가 정답이 된다.

 

이 두가지 규칙을 로직화 한게 아래 코드 이다.

 

class Solution { // 클래스 이름은 Solution 이다.

    

    static Map<String, Integer> values = new HashMap<>(); // 로마자와 아라비아 숫자를 키 밸류 쌍으로 다루기 위해 해쉬맵을 선언했다.

    

    static { // 로마숫자와 아라비아 숫자 쌍을 key - value 형식으로 HashMap에 put 한다.

        values.put("M", 1000);

        values.put("D", 500);

        values.put("C", 100);

        values.put("L", 50);

        values.put("X", 10);

        values.put("V", 5);

        values.put("I", 1);

    }

    

    public int romanToInt(String s) {

        int sum = 0; // return 할 int 변수를 선언 한다.

        int i = 0; // 루프에서 사용될 int 변수를 선언한다. 

        while(i<s.length()) { // 입력값의 글자 숫자 만큼 반복한다.

            String currentSymbol = s.substring(i, i + 1); // 입력값의 맨 i 번째 문자를 currentSymbol에 담는다.

            int currentValue = values.get(currentSymbol); // currentSymbol에 해당하는 아라비아 숫자를 currentValue에 담는다.

            int nextValue = 0; // 다름 숫자를 담을 int 변수를 선언한다. 

            if(i + 1 < s.length()) { // 입력값의 맨 마지막 글자까지 가지 않았다면 이 if 문을 실행한다.

                String nextSymbol = s.substring(i + 1, i+2); // currentSymbol 다음 글자를 nextSymbol에 담는다.

                nextValue = values.get(nextSymbol); // nextSymbol에 해당하는 아라비아 숫자를 nextValue에 담는다.

            }

            

            if(currentValue < nextValue) { // 현재 값이 다음 값보다 작을 경우 아래를 실행한다.

                sum += (nextValue - currentValue); // sum은 sum + (nextValue-currentValue) 가 된다.

                i += 2; // 입력값의 두 문자에 대해 실행 했기 때문에 두칸을 건너 뛰기 위해 i 에 2를 더한다.

            } else { // 현재 값이 다음 값보다 같거나 클 경우 아래를 실행한다.

                sum += currentValue; // 그냥 sum에다가 currentValue를 더한다.

                i +=1; // 한 글자에 대해서만 처리했으므로 i에 1을 더한다.

            }

        }

        return sum; // sum 값을 return 한다.

    }

}

 

이것과 같은 Python 스크립트는 아래와 같다.

 

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

class Solution:
    def romanToInt(self, s: str) -> int:
        total = 0
        i = 0
        while i < len(s):
            # If this is the subtractive case.
            if i + 1 < len(s) and values[s[i]] < values[s[i + 1]]:
                total += values[s[i + 1]] - values[s[i]]
                i += 2
            # Else this is NOT the subtractive case.
            else:
                total += values[s[i]]
                i += 1
        return total

 

조금 다르게 접근할 수도 있다.

 

아예 로마숫자와 아라비아 숫자 매칭을 아래와 같이 할 수 있다.

 

class Solution {
    
    static Map<String, Integer> values = new HashMap<>();

    static {
        values.put("I", 1);
        values.put("V", 5);
        values.put("X", 10);
        values.put("L", 50);
        values.put("C", 100);
        values.put("D", 500);
        values.put("M", 1000);
        values.put("IV", 4);
        values.put("IX", 9);
        values.put("XL", 40);
        values.put("XC", 90);
        values.put("CD", 400);
        values.put("CM", 900);
    }

 

이렇게 매칭을 만들면 로직은 아래와 같이 바꾸면 된다.

    public int romanToInt(String s) {
        
        int sum = 0;
        int i = 0;
        while (i < s.length()) {
            if (i < s.length() - 1) {
                String doubleSymbol = s.substring(i, i + 2); // 아예 처음부터 입력값의 글자 두 개를 불러 온다.
                // Check if this is the length-2 symbol case.
                if (values.containsKey(doubleSymbol)) { // 그 키 값이 위 매핑에 있다면 
                    sum += values.get(doubleSymbol); // 해당 값을 가져오고
                    i += 2; // 문자 두 개를 처리 했으니 i에 2를 더한다.
                    continue;
                }
            }
            // Otherwise, it must be the length-1 symbol case. 두 글자가 매핑에 없다면 
            String singleSymbol = s.substring(i, i + 1); // 한 글자만 불러와서 
            sum += values.get(singleSymbol); // sum 에 더해 준다.
            i += 1; // 한 글자만 처리했으니 i 에 1을 더해 준다.
        }
        return sum; // 결과 값을 리턴한다.
    }
}

 

여기에 해당하는 Python 코딩은 아래와 같다.

values = {
    "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
}

class Solution:
    def romanToInt(self, s: str) -> int:
        total = 0
        i = 0
        while i < len(s):
            # This is the subtractive case.
            if i < len(s) - 1 and s[i:i+2] in values:
                total += values[s[i:i+2]] 
                i += 2
            else:
                total += values[s[i]]
                i += 1
        return total

 

위 두 개는 입력값 을 왼쪽에서 오른쪽으로 보면서 계산한 것이다.

입력값을 오른쪽에서 부터 계산하는 방법도 생각해 볼 수 있다.

 

class Solution {
    
    static Map<String, Integer> values = new HashMap<>();
    
    static {
        values.put("M", 1000);
        values.put("D", 500);
        values.put("C", 100);
        values.put("L", 50);
        values.put("X", 10);
        values.put("V", 5);
        values.put("I", 1);
    }

    public int romanToInt(String s) {
        
        String lastSymbol = s.substring(s.length() - 1); // 맨 마지막 - 오른쪽 - 글자를 가져온다.
        int lastValue = values.get(lastSymbol); // 오른쪽 로마자에 해당하는 아라비아 숫자를 가져온다.
        int total = lastValue; // 리턴할  int 변수를 생성했다. 값은 lastValue를 넣었다.

        for (int i = s.length() - 2; i >= 0; i--) { // 입력값 -1 만큼 for 문을 돌린다. i 는 맨 마지막 글자 이전 부터 시작할 수 있도록 한다.
            String currentSymbol = s.substring(i, i + 1); // 현재값을 구한다. (첫번째 루프실행의 경우 맨 오른쪽에서 두번째 글자)
            int currentValue = values.get(currentSymbol); // 현재 값에 해당하는 아라비아 숫자를 구한다.
            if (currentValue < lastValue) { // 현재 값이 lastValue보다 작다면 
                total -= currentValue; // total = total - currentValue를 한다. 첫번쨰 루프에서 total은 lastValue가 된다.
            } else { // 현재 값이 lastValue보다 크거나 같다면
                total += currentValue; // total = total + currentValue를 한다. 
            }
            lastValue = currentValue; // lastValue에 currentValue를 입력한다.
        }
        return total; // for 문을 다 돌린 후 total 값을 리턴한다.
    }
}

 

여기에 해당하는 Python 스크립트는 아래와 같다.

 

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

class Solution:
    def romanToInt(self, s: str) -> int:
        total = values.get(s[-1])
        for i in reversed(range(len(s) - 1)):
            if values[s[i]] < values[s[i + 1]]:
                total -= values[s[i]]
            else:
                total += values[s[i]]
        return total