[LeetCode] - 13. Roman to Integer

LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '쉬움 (Easy)' 단계인 "Roman to Integer" 문제입니다.

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

 

문제 : 

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol	Value
I	1
V	5
X	10
L	50
C	100
D	500
M	1000

 

For example, 2 is written as II in Roman numeral, just two ones added together.

12 is written as XII, which is simply X + II.

The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV.

Because the one is before the five we subtract it making four.

The same principle applies to the number nine, which is written as IX.

There are six instances where subtraction is used: I can be placed before V (5) and X (10) to make 4 and 9.

X can be placed before L (50) and C (100) to make 40 and 90.

C can be placed before D (500) and M (1000) to make 400 and 900. Given a roman numeral, convert it to an integer.

---

Example 1 :

Input : s = "III"

Output : 3

Explanation : III = 3.

 

Example 2 :

Input : s = "LVIII"

Output : 58

Explanation : L = 50, V= 5, III = 3.

 

Example 3 :

Input : s = "MCMXCIV"

Output : 1994

Explanation : M = 1000, CM = 900, XC = 90 and IV = 4.

 

Constraints :

• 1 <= s.length <= 15
• s contains only the characters ('I', 'V', 'X', 'L', 'C', 'D', 'M').
• It is guaranteed that s is a valid roman numeral in the range [1, 3999].

---

이 문제는 로마 숫자는 I, V, X, L, C, D, M의 7가지 기호로 구성됩니다. 숫자는 왼쪽에서 오른쪽으로 큰 값에서 작은 값 순으로 쓰지만, 4와 9와 같은 경우에는 작은 값이 큰 값 앞에 와서 뺄셈을 의미합니다. 예를 들어, IV는 4, IX는 9를 의미하며, 주어진 로마 숫자를 정수로 변환하는 문제입니다. 처음에 이 문제를 봤을 때 쉬운데? 싶었지만, 4, 9 같은 숫자들을 변환할 때에 어려움을 겪었었습니다. 

class Solution {
    public int romanToInt(String s) {
        int num = 0;
        int res = 0;
        
        for (int i = s.length() - 1; i >= 0; i--) {
            switch (s.charAt(i)) {
                case 'I':
                    num = 1;
                    break;
                case 'V':
                    num = 5;
                    if (i > 0 && s.charAt(i - 1) == 'I') {
                        num = 4;
                        i--; // Skip the 'I' since it's part of a subtractive pair
                    }
                    break;
                case 'X':
                    num = 10;
                    if (i > 0 && s.charAt(i - 1) == 'I') {
                        num = 9;
                        i--; // Skip the 'I'
                    }
                    break;
                case 'L':
                    num = 50;
                    if (i > 0 && s.charAt(i - 1) == 'X') {
                        num = 40;
                        i--; // Skip the 'X'
                    }
                    break;
                case 'C':
                    num = 100;
                    if (i > 0 && s.charAt(i - 1) == 'X') {
                        num = 90;
                        i--; // Skip the 'X'
                    }
                    break;
                case 'D':
                    num = 500;
                    if (i > 0 && s.charAt(i - 1) == 'C') {
                        num = 400;
                        i--; // Skip the 'C'
                    }
                    break;
                case 'M':
                    num = 1000;
                    if (i > 0 && s.charAt(i - 1) == 'C') {
                        num = 900;
                        i--; // Skip the 'C'
                    }
                    break;
            }
            res = res + num;
        }

        return res;

    }
}

 

솔직히 이 코드는 리스트에다가 넣어서 썼을 수도 있었지만 저는 가장 심플한 방법이 좋아서 좀 길더라도 스위치 케이스 조건문을 썼습니다 : 

 

1. 변수 초기화 :
   • num은 현재 문자의 값을 저장합니다.
   • res는 최종 결과 값을 저장합니다.
2. 문자열을 오른쪽에서 왼쪽으로 순회 :
   • 문자열을 오른쪽에서 왼쪽으로 순회하면서 각 문자의 값을 num에 저장합니다.
   • 감산이 필요한 경우(예: 'IV', 'IX') 이전 문자를 확인하고 값을 수정하며 인덱스를 건너뜁니다.
   • num 값을 res에 더합니다.
3. 결과 반환 :
   • 최종 결과 값을 반환합니다.

시간 및 공간 복잡도:

1. 시간 복잡도 :
   • 문자열의 각 문자를 한 번씩 순회하므로 시간 복잡도는 O(n)입니다. 여기서 n은 문자열의 길이입니다.
2. 공간 복잡도:
   • 추가적인 데이터 구조를 사용하지 않고, 고정된 변수만 사용하므로 공간 복잡도는 O(1)입니다.]

복잡도들을 보면 아주 효율적인 코드라고 볼 수 있겠습니다. 

---

코드 Runtime 결과