리트코드 - 13. Roman to Integer

리트코드 - 13. Roman to Integer

출처 - https://leetcode.com/problems/roman-to-integer/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

로마 숫자는 I, V, X, L, C, D 및 M이라는 일곱 가지 다른 기호로 나타냅니다.

기호	값
I	1
V	5
X	10
L	50
C	100
D	500
M	1000

예를 들어, 2는 로마 숫자로 II로 나타내며, 그냥 두 개의 1을 더한 것입니다. 12는 XII로 나타내며, 이는 X + II로 간단히 나타낼 수 있습니다. 숫자 27은 XXVII로 나타내며, 이는 XX + V + II입니다.

로마 숫자는 일반적으로 왼쪽에서 오른쪽으로 큰 순서대로 작성됩니다. 그러나 4를 나타내는 숫자는 IIII가 아닙니다. 대신, 숫자 네는 IV로 쓰입니다. 왜냐하면 1이 5 앞에 있으므로 4를 만들기 위해 빼기를 합니다. 마찬가지로 9로 나타내는 원리는 IX로 나타냅니다. 여기서 빼기가 사용되는 경우는 다음과 같이 여섯 가지입니다:

• I는 5 (V) 및 10 (X) 앞에 배치하여 4와 9를 만들 수 있습니다.
• X는 50 (L) 및 100 (C) 앞에 배치하여 40과 90을 만들 수 있습니다.
• C는 500 (D) 및 1000 (M) 앞에 배치하여 400과 900을 만들 수 있습니다.

로마 숫자가 주어지면 정수로 변환하세요.

 

의사코드

함수 romanToInt (string s)     answer = 0     prev = 0 // 이전 숫자     반복문 시작 (s를 거꾸로 순회)         s에서 한글자 뗴서 c에 저장(char형)         current = getValue(c)                 if (current >= prev)              answer에 current 추가         else              answer에 current 뺌              prev = current     반복문 종료 answer 리턴 함수 getValue (char c)     I면 1 리턴     V면 5 리턴     X면 10 리턴     L면 50 리턴     C면 100 리턴     D면 500 리턴     M면 1000 리턴

 

풀이코드

class Solution {
    public int romanToInt(String s) {
        int answer = 0;
        int prev = 0;
        for (int i =  s.length() - 1; i >= 0; i--) {
            char c = s.charAt(i);
            int current = getValue(c);

            if (current >= prev) {
                answer += current;
            } else {
                answer -= current;
            }

            prev = current;
        
        }
        return answer;
    }

    private int getValue(char c) {
        switch(c) {
            case 'I':
                return 1;
            case 'V':
                return 5;
            case 'X':
                return 10;
            case 'L':
                return 50;
            case 'C':
                return 100;
            case 'D':
                return 500;
            case 'M':
                return 1000;
            default :
                return 0;
        }
    }
}

코드설명

문자열을 쪼개서 판단하는 문제이다.

로마 숫자도 일반 숫자와 마찬가지로 천의 자리, 백의 자리, 십의 자리, 일의 자리 순으로 되어있다.

하지만 자릿수대로 읽으려고 하면 중간중간 끼어드는 문자들 때문에 조금 번거로워진다.

 

예를 들어 14를 읽을때에 그냥 일반 숫자는 1하고 5읽으면 그만이지만, 로마숫자로는 XIV가 되기 때문에 순차적으로 읽으면 10+1+5 = 16이 된다.

반복문을 돌리자니 쪼개기가 다소 애매하다. 1개씩 쪼갤것인가 2개씩 쪼갤 것인가..?

 

생각을 조금 바꿔서 거꾸로 1의 자리부터 읽어보자.

 

1~3까지는 I, I+I, I+I+I 가 될 것이고

4는 I+V,

6~8은 V+I, V+I+I, V+I+I+I,

9는 I+X가 된다.

 

거꾸로부터 읽으면 큰 수 다음 작은수가 나왔을 때 -1을 하면 된다.

4는 (-1)+5=4 가 되고, 9는 (-1)+10=9 가 된다.

 

처음의 예를 다시 보면 X + I + V 에서 V가 5이므로 먼저 더하고, 작은 수인 I 나왔으니 -1하고, 다시 큰 수가 나왔으니 10을 하면 14가 제대로 나온다.

 

위의 코드에서는 prev값을 이전 값으로 하여, current값을 계속 받아와서 이전값과 비교하여 current가 prev보다 같거나 크면 더하고, 작으면 빼는 로직을 만들었다.

 

물론 이 문자열이 의미하는 숫자에 대한 getValue 값을 가져와야 비교가 가능하다.

 

시간복잡도 - O(n)

공간복잡도 - O(1)

 

문제를 풀며 생각한 흐름과 배운 점

하드코딩

class Solution {
    public int romanToInt(String s) {
        int answer = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (i + 1 == s.length()) {
                if (c == 'I') {
                    answer += 1;
                } if (c == 'V') {
                    answer += 5;
                } if (c == 'X') {
                    answer += 10;
                } if (c == 'L') {
                    answer += 50;
                } if (c == 'C') {
                    answer += 100;
                } if (c == 'D') {
                    answer += 500;
                } if (c == 'M') {
                    answer += 1000;
                }

                break;
            }
            
            char c2 = s.charAt(i + 1);
            if (c == 'I') {
                if (c2 == 'V') {
                    answer += 4;
                    i++;
                } else if (c2 == 'X') {
                    answer += 9;
                    i++;
                } else {
                    answer += 1;
                }
            }


            if (c == 'X') {
                if (c2 == 'L') {
                    answer += 40;
                    i++;
                } else if (c2 == 'C') {
                    answer += 90;
                    i++;
                } else {
                    answer += 10;
                }
            }
            if (c == 'C') {
                if (c2 == 'D') {
                    answer += 400;
                    i++;
                } else if (c2 == 'M') {
                    answer += 900;
                    i++;
                } else {
                    answer += 100;
                }
            }
                 if (c == 'V') {
                    answer += 5;
                } if (c == 'L') {
                    answer += 50;
                } if (c == 'D') {
                    answer += 500;
                } if (c == 'M') {
                    answer += 1000;
                }
        }
        return answer;
    }
}

처음에는 딱히 아이디어가 떠오르지 않아 하드코딩 했다.

투포인터를 쓰자니 앞뒤로 다루기 다소 애매했고, 처음에는 모든 경우의 수를 다 고려해서 배열에 넣고 가져오는 방식으로 할까하다가 string을 자르기가 좀 애매해서 하드코딩을 해봤다.

 

숫자가 크지 않기 때문에 이것이 가능했지만, 분기를 나누는 아이디어가 필요해서 조금 더 고민하다 나온 결과가 위의 코드이다.

 

정리

특정 문자열에서 분기가 나눠질 때엔 순방향,역방향 모두 고려해볼것.