[LeetCode] Roman to Integer 풀이

내 풀이

• 시간복잡도
  • O(N)
• 공간복잡도
  • O(1)

import java.util.*;

class Solution {

    public int romanToInt(String s) {
        int result = 0;

        Map<String, Integer> map = new HashMap<>();
        map.put("IV", 4);
        map.put("IX", 9);
        map.put("XL", 40);
        map.put("XC", 90);
        map.put("CD", 400);
        map.put("CM", 900);
        map.put("I", 1);
        map.put("V", 5);
        map.put("X", 10);
        map.put("L", 50);
        map.put("C", 100);
        map.put("D", 500);
        map.put("M", 1000);

        int length = s.length();
        if (length == 1) {
            return map.get(s);
        }

        String[] romans = s.split("");
        for (int i = 0; i < length; i++) {
            String current = romans[i];
            
            int nextIndex = i + 1;
            if(nextIndex >= length) {
                result += map.get(current);
                continue;
            }
            String next = romans[nextIndex];

            Integer value = map.get(current + next);
            if (value != null) {
                result += value;
                i++;
                continue;
            }

            result += map.get(current);
        }
        
        return result;
    }
}

최적화

• 시간복잡도
  • O(N)
• 공간복잡도
  • O(1)
• 가장 큰 로마 숫자가 왼쪽에서부터 오른쪽으로 향하는데, 결합문자의 경우는 작은숫자 다음 큰숫자가 오는 것을 이용

import java.util.*;

class Solution {
    public int romanToInt(String s) {
        int result = 0;
        int length = s.length();
        
        Map<Character, Integer> map = new HashMap<>();
        map.put('I', 1);
        map.put('V', 5);
        map.put('X', 10);
        map.put('L', 50);
        map.put('C', 100);
        map.put('D', 500);
        map.put('M', 1000);
        
        for (int i = 0; i < length; i++) {
            int currentValue = map.get(s.charAt(i));
            
            if (i < length - 1 && currentValue < map.get(s.charAt(i + 1))) {
                result -= currentValue;
            } else {
                result += currentValue;
            }
        }
        
        return result;
    }
}