[LeetCode] 13.Roman to Integer

문제

분석

• 주어진 로마문자를 수로 변경해서 더한다.
• 단 예외가 있다.
• 아래 처럼 문자가 이루어져 있는 경우는 다음 값을 따른다.
  - "IV", 4, "IX", 9
  - "XL", 40, "XC", 90
  - "CD", 400, "CM", 900
• 좀더 분석을 해보면
  - 앞에 놓여진 문자의 값 보다 뒤에 있는 문자의 값이 크면 
  - IV 인경우 V(뒤에 있는 문자값) - I(앞에 있는 문자값) 이 된다.

 

구현1 (무식하게 구현해보기)

class Solution {
    
    private Map<String, Integer> numberMap = new HashMap<>();
    private Map<String, Integer> complexNumberMap = new HashMap<>();
       
    private class RomanScore {
        public StringBuffer s;
        public int score;
        
        public RomanScore(StringBuffer s, int score) {
            this.s = s;
            this.score = score;
        }
        
        public void addNumber(int score) {
            this.score+=score;
        }
    }
    
    private void init() {
        numberMap.put("I", 1);
        numberMap.put("V", 5);
        numberMap.put("X", 10);
        numberMap.put("L", 50);
        numberMap.put("C", 100);
        numberMap.put("D", 500);
        numberMap.put("M", 1000);
        complexNumberMap.put("IV", 4);
        complexNumberMap.put("IX", 9);
        complexNumberMap.put("XL", 40);
        complexNumberMap.put("XC", 90);
        complexNumberMap.put("CD", 400);
        complexNumberMap.put("CM", 900);
    }
    
    
    
    public RomanScore complexNumber(RomanScore score) {
        int totalNumber = 0;
        StringBuffer s = score.s;
  
        for (String key : complexNumberMap.keySet()) {
            if (s.indexOf(key) >= 0) {
                totalNumber += complexNumberMap.get(key);
                s.delete(s.indexOf(key), s.indexOf(key)+2);
            }
        }
    
        score.s = s;
        score.score = totalNumber;
        return score;
    }
   
     public RomanScore simpleNumber(RomanScore score) {
         int totalNumber = 0;
         if (score.s.length() <= 0) {
             return score;
         }
         
         int count = 1;
         char pre = score.s.charAt(0);
         for(int i = 1; i < score.s.length(); i++) {
             if (pre != score.s.charAt(i)) {
                 int num = numberMap.get(Character.toString(pre));
                 totalNumber = totalNumber + num * count;
                 pre = score.s.charAt(i);
                 count = 1;
             } else {
                 count++;   
             }
         }
         
         if (count != 0) {
             int num = numberMap.get(Character.toString(pre));
             totalNumber = totalNumber + num * count;
         }
         
         score.addNumber(totalNumber);
         return score;
     }
    
    
    public int romanToInt(String s) {   
        init();
        RomanScore score = new RomanScore(new StringBuffer(s), 0);
        score = complexNumber(score);
        score = simpleNumber(score);
        return score.score;
    }
}

 

결과1

 

구현2 (심플하게 구현하기)

class Solution {
    
    private Map<Character, Integer> numberMap = new HashMap<>();

    private void init() {
        numberMap.put('I', 1);
        numberMap.put('V', 5);
        numberMap.put('X', 10);
        numberMap.put('L', 50);
        numberMap.put('C', 100);
        numberMap.put('D', 500);
        numberMap.put('M', 1000);
    }
    
    
    public int solve(String s) {
        int totalNumber = 0;
        for(int i = 0; i < s.length()-1; i++) {
            int currentNumber = numberMap.get(s.charAt(i));
            int nextNumber = numberMap.get(s.charAt(i+1));
            
            if (currentNumber < nextNumber) {
                totalNumber = (totalNumber - currentNumber);
            } else {
                totalNumber += (currentNumber);      
            }
        }
        
        totalNumber += numberMap.get(s.charAt(s.length()-1));
        return totalNumber;
    }
    
    public int romanToInt(String s) {   
        init();
        int answer = solve(s);
        return answer;
    }
}

 

결과2

 

 

결론

속도가 조금 느려도 1번이 메모리 면에서 4MB 가 차이난다.

 

 

릿코드

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

Roman to Integer - LeetCode