[leetcode] Roman to Int

 

제약 조건

문자열의 크기는 15

문자열에 들어갈 수 있는 알파벳은 7개뿐..

아무리 커도 3999까지밖에 안된다.. 그러니까.. I, ...., MMMCMXCIX 까지...

 

제출한 코드

문제를 제대로 안 읽고 되는대로 풀고 제출한 코드..

문자열의 크기가 15였기 때문에 시간복잡도가 많이 커질 일이 없다고 생각했고 계산할 필요도 없지 않나 하고 생각함..

import java.util.Map;
import java.util.HashMap;
import java.util.StringTokenizer;

class Solution {
    public int romanToInt(String s) {
        int answer = 0;
        Map<String, Integer> roman = new HashMap<>();
        roman.put("I", 1);
        roman.put("V", 5);
        roman.put("X", 10);
        roman.put("L", 50);
        roman.put("C", 100);
        roman.put("D", 500);
        roman.put("M", 1000);
        
        String[] st = s.split("");
        for(int i = 0, size = st.length; i < size; i++) {
            String t = st[i];
            if (t.equals("I") && i + 1 < size) {
                if (st[i + 1].equals("V")) {
                    answer += 4;
                    i+=1;
                    continue;
                } else if (st[i + 1].equals("X")) {
                    answer += 9;
                    i+=1;
                    continue;
                }
            } else if (t.equals("X") && i + 1 < size) {
                if (st[i + 1].equals("L")) {
                    answer += 40;
                    i+=1;
                    continue;
                } else if (st[i + 1].equals("C")) {
                    answer += 90;
                    i+=1;
                    continue;
                }
            } else if (t.equals("C") && i + 1 < size) {
                if (st[i + 1].equals("D")) {
                    answer += 400;
                    i+=1;
                    continue;
                } else if (st[i + 1].equals("M")) {
                    answer += 900;
                    i+=1;
                    continue;
                }
            }
            
            answer += roman.get(t);
        }
        return answer;
    }
}

위와 같이 풀고 이렇게 푸는게 맞나하는 생각을 하게 되었고 discussion을 살펴보니 이후값과 비교하는 코드가 굉장히 많았다.

 

뭐지..? 저런 조건이 있나..? 하고 살펴보다가 비로소 문제를 제대로 읽게 되었다.

 

문제

 

Roman numerals는 I, V, X, L, C, D, M 7개의 심볼로 이루어져 있다.

 

예를 들어, 2는 Roman numeral로 II로 쓰고 두 개를 더 하면 된다.

12는 XII라고 쓰고 단순히 X + II 이다.

27은 XXVII라고 쓰고 XX + V + II로 보면 된다.

 

Roman numerals는 제일 큰 수부터 제일 작은 수 순서로 왼쪽에서 오른쪽으로 쓴다.

하지만, 4는 IIII가 아니다. 대신, 4는 IV로 쓴다. 왜냐하면 5 이전에 있는 1은 5에서 1을 빼고 4로 만드는 용도로 사용한다.

똑같은 principle(원칙)은 9에도 적용돼서, IX로 쓴다.

이러한 뺄셈을 사용하는 여섯 개의 예시가 있다.

 

V(5)와 X(10) 앞에 I를 놓아 4와 9를 만들 수 있다.

L(50)와 C(100) 앞에 X를 놓아 40와 90을 만들 수 있다.

D(500)와 M(1000) 앞에 C를 놓아 400와 900을 만들 수 있다.

 

위와 같이 문제를 읽고 다시 풀어보았다.

제출한 코드

import java.util.Map;
import java.util.HashMap;
import java.util.StringTokenizer;

class Solution {
    public int romanToInt(String s) {
        int answer = 0;
        Map<String, Integer> roman = new HashMap<>();
        roman.put("I", 1);
        roman.put("V", 5);
        roman.put("X", 10);
        roman.put("L", 50);
        roman.put("C", 100);
        roman.put("D", 500);
        roman.put("M", 1000);
        
        String[] st = s.split("");
        for(int i = 0, size = st.length; i < size; i++) {
            String t = st[i];
            if(i + 1 < size && roman.get(st[i + 1]) > roman.get(t)) {
                answer -= roman.get(t);
            } else {
                answer += roman.get(t);
            }
        }
        return answer;
    }
}

오히려 더 안 좋은 결과가 나왔다..? ㅎㅎ

 

 

위와 비슷한 로직으로 풀되 좀 더 나은 풀이를 찾아보기로 했다.

 

Discussion에 있던 로직

돌려보니 아래와 같은 결과가 나왔다.

class Solution {
    public int romanToInt(String s) {
        int answer = 0, number = 0, prev = 0;

        for (int j = s.length() - 1; j >= 0; j--) {
            switch (s.charAt(j)) {
                case 'M' -> number = 1000;
                case 'D' -> number = 500;
                case 'C' -> number = 100;
                case 'L' -> number = 50;
                case 'X' -> number = 10;
                case 'V' -> number = 5;
                case 'I' -> number = 1;
            }
            if (number < prev) {
                answer -= number;
            }
            else {
                answer += number;
            }
            prev = number;
        }
        return answer;
    }
}

특징을 꼽아보자면,

1. 로만 숫자 심볼을 찾을때 char형 사용

2. Map이 아닌 switch문 사용

 

하나씩 적용해보면서 보기로 했다.

 

로만 숫자 심볼을 찾을 때 char형 사용

import java.util.Map;
import java.util.HashMap;
import java.util.StringTokenizer;

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

13ms로 줄었다. String보다는 char형을 쓰는 것이 더 좋은 것 같다.

 

String과 char의 차이에 대해서도 블로그에 정리하면 좋을 것 같은데 일단 String은 참조형이고 char은 기본형이다.

비교할 때도 String은 equals를 이용해서 비교해야하지만 char은 = 을 이용해서도 비교 가능하다.

 

비교 과정만 봐도 절차가 필요한 String과 다르게 바로 비교된다는 점에서 char형이 빠른 것은 어찌보면 당연하다..

 

Map이 아닌 switch문 사용

class Solution {
    public int romanToInt(String s) {
        int answer = 0;
        
        String[] st = s.split("");
        int value = 0, prev = 0;
        for(int i = st.length - 1; i >= 0; i--) {
            String t = st[i];
            
            switch(t) {
                case "I": 
                    value = 1;
                    break;
                case "V": 
                    value = 5;
                    break;
                case "X": 
                    value = 10;
                    break;
                case "L": 
                    value = 50;
                    break;
                case "C": 
                    value = 100;
                    break;
                case "D": 
                    value = 500;
                    break;
                case "M": 
                    value = 1000;     
                    break;
            }
            
            if(value < prev) {
                answer -= value;
            } else {
                answer += value;
            }
            prev = value;
        }
        return answer;
    }
}

map을 안쓰는 것만으로도 꽤 많이 줄었다. 비교 방식의 변화도 있기 때문에 고려해야한다.

 

원래 앞에서부터 가다가 뒤에 큰 수가 나오면 앞에 있는 수를 빼는 식으로 구현하였다.

그런데 위에서는 뒤에서부터 앞에 작은 수가 나오면 현재 나온 수를 빼는 식으로 구현하였다.

 

 

느낀 점

String을 안 쓸 수 있으면 최대한 자제하자.

문제를 똑바로 읽자..