Leetcode 13. Roman to Integer

문제

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

(easy)

 

정답

class Solution {
    public int romanToInt(String s) {
        Map<Character, Integer> val = new HashMap<>();
        val.put('I',1);
        val.put('V', 5);
        val.put('X', 10);
        val.put('L', 50);
        val.put('C', 100);
        val.put('D', 500);
        val.put('M', 1000);

        int sum = 0;

        for (int i = 0; i<s.length(); i++){
            int cur = val.get(s.charAt(i));
            int next = 0;
            if (i + 1 < s.length()){
                next = val.get(s.charAt(i+1));
            } else {
                next = 0;
            }

            if (cur < next) {
                sum -= cur;
            } else {
                sum += cur;
            }
        }
        return sum;    
    }
}

 

결과

다소 별로임

 

 

포인트

 

1. 문자열을 순회하는 기본 패턴

for (int i = 0; i < s.length(); i++) 

s.charAt(i) 사용.

 

 

2. 문자(char)와 값(int)의 매핑

문자 → 숫자 변환 구조에서 

Map<Character, Integer> 사용.

 

 

3. 현재 값 vs 다음 값과 비교하는 알고리즘 사고

비교 시에는 i + 1 < length 범위 체크. OutOfBounds 주의

if (i + 1 < s.length()) {
	next = val.get(s.charAt(i+1));
} else {
	next = 0;
}

 

그리고 마지막 문자 처리는 next = 0 

 

4. IV, IX, XL, XC, CD, CM 하드코딩 대신 

cur < next 이런 식으로

 

5. 누적 합(sum) 계산은 += / -=

 

 

더 효율적인 방법

 

1. HashMap 없애고 switch로 바로 값 뽑기

class Solution {
    private int value(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;
            default:  return 1000; // 'M'
        }
    }

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

        for (int i = 0; i < s.length(); i++) {
            int cur = value(s.charAt(i));
            int next = (i + 1 < s.length()) ? value(s.charAt(i + 1)) : 0;

            sum += (cur < next) ? -cur : cur;
        }
        return sum;
    }
}

 

switch문은 문자 하나를 받으면, 그에 대응하는 숫자를 바로 반환하는 구조.

객체 생성 비용 없이 빠르게 매핑할 수 있고, 가독성도 좋다.

 

2. 문자 테이블(배열)로 매핑

class Solution {
    public int romanToInt(String s) {
        int[] val = new int[128];
        val['I'] = 1; val['V'] = 5; val['X'] = 10; val['L'] = 50;
        val['C'] = 100; val['D'] = 500; val['M'] = 1000;

        int sum = 0;
        for (int i = 0; i < s.length(); i++) {
            int cur = val[s.charAt(i)];
            int next = (i + 1 < s.length()) ? val[s.charAt(i + 1)] : 0;
            sum += (cur < next) ? -cur : cur;
        }
        return sum;
    }
}

 

문자(char)를 인덱스로 써서, 바로 값(int)을 꺼내는 방식이다.

문자(char) → ASCII 코드 → 배열 인덱스 이런 식.

 

char 는 유니코드라서 ('I' = 73 이런 식으로)

int[] val = new int[128]; // ASCII 범위
val['I'] = 1; 이렇게도 할 수 있다.

 

특히 문자 개수가 고정되어 있어서 HashMap 대신 문자 테이블 배열로 매핑할 수 있고 

char 값을 바로 인덱스로 사용해 접근 비용을 줄이는 장점이 있다.