LeetCode 12 - Integer to Roman

https://leetcode.com/problems/integer-to-roman

 

Symbol 별로 숫자가 할당되어 있다.

10진수의 수를 이제 로마수로 변경해야 한다. 변경은 다음과 같은 과정을 통한다.

1. 수가 4 혹은 9로 시작하지 않는다면 input으로부터 뺄 수 있는 최대 symbol을 선택한다. 그리고 해당 symbol을 결과에 추가한다. 그리고 해당 숫자를 뺀 나머지를 로마수로 재할당한다.
2. 만약 수가 4 혹은 9로 시작하다면, 해당 값을 뺄샘 형태로 변환하여 로마수로 표현한다. 예를 들어 4는 5(V)에서 1(I)을 뺀 값이 되므로 IV가 된다.
3. 10의 거듭제곱은 최대 3번까지 연속해서 붙일 수 있다. 하지만 5(V), 50(L), 500(D)은 여러 번 반복해서 사용할 수 없다. 만약 어떤 기호가 4번 반복해서 사용해야 할 경우에는 뺄셈 형태로 변환한다.

우선 하나씩 생각해보자.

주어진 숫자 num의 첫자리 숫자를 어떻게 판단 할 것인가?

4냐 400이냐에 따라 조합이 달라지기 때문에 첫 자리 숫자가 어떤 수인지를 넘어 자릿수까지 판단을 해야 한다.

문자열로 판단하는 게 낫겠다는 생각이 든다. int num = 3749라고 가정해 보자.

문자열로 바꾸면 “3749”, 길이가 4인 문자열이 된다.

첫자리는 3 * 10 ^4 그다음은 7 * 10^3, 410^2, 910^1 이렇게 된다. 매 순간 판단하는 숫자가 문자열의 길이와 chartAt(n)으로 편리하게 구할 수 있다.

class Solution {

    private static final Map<Integer, String> symbolMap = new LinkedHashMap<>();

    static {
        symbolMap.put(1000, "M");
        symbolMap.put(500, "D");
        symbolMap.put(100, "C");
        symbolMap.put(50, "L");
        symbolMap.put(10, "X");
        symbolMap.put(5, "V");
        symbolMap.put(1, "I");
    }

    public String intToRoman(int num) {
        StringBuilder sb = new StringBuilder();
        String number = Integer.toString(num);
        int length = number.length();

        for (int i = 0; i < length; i++) {
            int coefficient = number.charAt(i) - '0';
            int exponent = length - i - 1;
            
            int now = coefficient * (int)Math.pow(10, exponent);
            
            if (coefficient == 4 || coefficient == 9) {
                for (int key : symbolMap.keySet()) {
                    if (key > now && symbolMap.containsKey(key - now)) {
                        sb.append(symbolMap.get(key - now));
                        sb.append(symbolMap.get(key));
                    }
                }
            } else {
                for (int key : symbolMap.keySet()) {
                    while (now >= key) {
                        now -= key;
                        sb.append(symbolMap.get(key));
                    }
                }
            }
        }

        return sb.toString();
    }
}

일단 통과는 됐다.

간단하게 설명하자면 우선 LinkedHashMap을 사용해 데이터를 삽입된 순서대로 저장되도록 처리했다.

그 후 주어진 num을 문자로 변경하고 이 문자열을 조작해 문제를 풀었다.

그런데 매 숫자마다 일일이 확인하고 변환하는 과정 때문에 효율적이지 않다.

그러면 애초에 가능한 로마 symbol을 다 저장해 놓으면 되는 거 아닐까? 생각보다 개수가 몇 개 없으니 가능한 방식이다.

class Solution {

    private static final Map<Integer, String> SYMBOL_MAP = new LinkedHashMap<>();

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

    public String intToRoman(int num) {
        StringBuilder sb = new StringBuilder();

        for (int key : SYMBOL_MAP.keySet()) {
            while (num >= key) {
                num -= key;
                sb.append(SYMBOL_MAP.get(key));
            }
        }

        return sb.toString();
    }
}

그런데 더 개선할 점이 있는 것 같다.

데이터셋 저장을 LinkedHashMap을 사용함으로써 삽입 순서를 유지한 것은 좋았지만 각 반복에서 Map의 엔트리에 접근하는 데 추가적인 동작이 들어간다.

LinkedHashMap은 내부적으로 LinkedList를 사용하니까 메모리 접근이 배열에 비해서 덜 효율적일 수 있다.

따라서 해당 저장을 두 개의 배열로 나누어 저장해서 접근하면 조금 더 효율적인 결과를 얻을 수 있을 것이다.

class Solution {
    private static final int[] VALUES = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    private static final String[] SYMBOLS = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

    public String intToRoman(int num) {
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < VALUES.length; i++) {
            while (num >= VALUES[i]) {
                num -= VALUES[i];
                sb.append(SYMBOLS[i]);
            }
        }

        return sb.toString();
    }
}

이 문제는 결국 공간과 시간의 트레이드오프를 보여줬던 문제였던 것 같다.