LeetCode - Roman to Integer

Roman to Integer - LeetCode

 

 

나의 풀이

class Solution {
    public int romanToInt(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        
        final Map<String, Integer> romanMap = getRomanMap();
        if (s.length() == 1) {
            return romanMap.get(s);
        }
        
        final String[] letters = s.split("");
        int answer = 0;
        for (int idx = letters.length - 1; idx > 0; idx--) {
            if (romanMap.get(letters[idx]) <= romanMap.get(letters[idx - 1])) {
                answer += romanMap.get(letters[idx]);
            } else {
                answer += romanMap.get(letters[idx]) - romanMap.get(letters[idx - 1]);
                idx--;
            }
        }
        if (romanMap.get(letters[1]) <= romanMap.get(letters[0])) {
            return answer + romanMap.get(letters[0]);
        }
        return answer;
    }
    
    private Map<String, Integer> getRomanMap() {
        return Map.ofEntries(
            Map.entry("M", 1000),
            Map.entry("D", 500),
            Map.entry("C", 100),
            Map.entry("L", 50),
            Map.entry("X", 10),
            Map.entry("V", 5),
            Map.entry("I", 1)
        );
    }
}

 

 

떠올린 방법

- 뒤에서부터 문자를 돌면서 만약 앞의 문자가 현재 문자보다 작은 수를 나타낸다면 현재 문자 - 앞의 문자의 수를 구해 더해주는 방식

- time complexity : O(n)

- space complexity : O(n)

 

 

결과

성능이 크게 좋아보이지는 않은..

 

 

---

솔루션

 

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;

        for (int i = s.length() - 2; i >= 0; i--) {
            String currentSymbol = s.substring(i, i + 1);
            int currentValue = values.get(currentSymbol);
            if (currentValue < lastValue) {
                total -= currentValue;
            } else {
                total += currentValue;
            }
            lastValue = currentValue;
        }
        return total;
    }
}

제일 좋은 풀이가 나와 같이 오른쪽에서부터 왼쪽으로 iteration을 도는 방식이다

다만 나와는 다르게 lastValue를 사용해서 코드가 좀 더 깔끔해졌다